תרגום ביטויים מפורשים לסדרי גדילה
[עריכה]
נתונות שתי פונקציות:
![{\displaystyle \displaystyle f(n)=n+c_{1}n\log ^{2}(n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4b10ff2cb4632bf4b104e99f684688d34dd0ce4d)
![{\displaystyle \displaystyle g(n)=n+c_{2}n^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8c973cc2997dec311fbf99aab37550fed8e95958)
כאשר
.
- האם
?
- האם
?
ראשית נראה ש
.
הוכחה: ![{\displaystyle \displaystyle \lim _{n\rightarrow \infty }{\frac {f(n)}{g(n)}}=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/843aeb5ab21646536c49d09f4b41fb03dbb2cb06)
![{\displaystyle \displaystyle \lim _{n\rightarrow \infty }{\frac {n+c_{1}n\log ^{2}(n)}{n+c_{2}n^{2}}}=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dbbd6293ef625846ef5bf20d0fd8acd733235fba)
![{\displaystyle \displaystyle \lim _{n\rightarrow \infty }{\frac {{\frac {1}{n}}+c_{1}{\frac {1}{n}}\log ^{2}(n)}{{\frac {1}{n}}+c_{2}}}=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/954f63694d10c80fb3a23711379e79fab19e25f0)
הטענה נובעת, לכן, מכלל הגבולות בסדרי גדילה.
כעת נראה כי
הוכחה: נניח בשלילה כי
.
אז קיים
כך שעבור ערכי
גדולים מספיק,
.
נחלק את שני האגפים ב
(נזכר שהוא חיובי), ונקבל
עבור ערכי
גדולים מספיק.
ניקח גבול של שני האגפים, ונקבל
.
אבל במקרה כאן, קל לראות שהגבול שואף לאינסוף, ולכן אין קבוע שחוסם אותו מלמעלה.
שאלה בסיסית ביחסים
[עריכה]
אנא הוכח או הפרך את הטענות הבאות:
.
.
.
.
.
|
שימו לב: הכוונה בסעיף הראשון לפונקציה הקבועה , ולא לקבוע 80.
|
נכון.
הוכחה: נבחר
ו
, ונוודא
.
נכון.
הוכחה: נבחר
ו
, ונוודא
.
נכון.
הוכחה: נבחר
ו
, ונוודא
.
לא נכון.
הוכחה: נניח בשלילה שהטענה נכונה, ולכן עבור
ו
כלשהם,
.
אם נציב
נקבל
![{\displaystyle \displaystyle (3\cdot n)|^{n_{0}+\left\lceil c\right\rceil }=3\cdot n_{0}+3\cdot \left\lceil c\right\rceil \leq }](https://wikimedia.org/api/rest_v1/media/math/render/svg/6faedec7d699fcd1a1569dadb7462040c9979e1d)
![{\displaystyle \displaystyle (c\cdot 1)|^{n_{0}+\left\lceil c\right\rceil }=c,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/183a45bdb85cb00d0e462318162a7cec6c7534db)
שאינו הגיוני.
נכון.
הוכחה: באופן כללי,
, ולכן הביטויים הם למעשה אותו ביטוי עד כדי הכפלה בקבוע.
אנא הוכח את כלל האדיטיביות ל
:
לכל
,
.
ההוכחה דומה למדי להוכחת האדיטיביות שראינו בהרצאה:
הוכחה: (1) עפ"י ההגדרה:
משמעו שלכל
,
, עבור
כלשהם.
משמעו שלכל
,
, עבור
כלשהם.
לכן:
- לכל
,
.
- לכל
,
.
מקבלים את התוצאה ע"י חיבור שני האי-שוויונים האחרונים.
אנא הוכח את טרנזיטיביות ל
:
לכל
,
.
ההוכחה דומה למדי להוכחת הטרנזיטיביות שראינו:
(1) עפ"י ההגדרה:
משמעו שלכל
,
, עבור
כלשהם.
משמעו שלכל
,
, עבור
כלשהם.
לכן:
- לכל
,
.
- לכל
,
.
מקבלים את התוצאה ע"י הצבת שני האי-שוויונים האחרונים אחד בשני:
- לכל
,
.
עוד כללים בסדרי גדילה
[עריכה]
הן פונקציות חיוביות ממש. אנא הוכח או הפרך כ"א מהכללים הבאים:
![{\displaystyle \displaystyle f(n)=O(g(n))\Rightarrow g(n)=O(f(n))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/49d6576f801050d075b2c4d037ccc39ae3471ca6)
![{\displaystyle \displaystyle f(n)+g(n)=\Theta (min\{f(n),g(n)\})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a95b45c0219149f7387cfd1ca245ab50b92b27e7)
![{\displaystyle \displaystyle f(n)=O(g(n))\Rightarrow 2^{f(n)}=O(2^{g(n)})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bf644bc8215ffdfb1c2901225968fb94989f8fc0)
![{\displaystyle \displaystyle f(n)+\Theta (f(n))=\Theta (f(n))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/86af88d12eafc742625355c49e8a19914067e68f)
![{\displaystyle \displaystyle f(n)=2^{\log(n)},g(n)=(\log(n))^{\log(n)}\Rightarrow f(n)=O(g(n))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e2fe50b3080ab5dd7c85f51d3450b95916789af4)
(לתזכורת,
הן פונקציות חיוביות ממש.)
- לא נכון. נפריך ע"י
.
- לא נכון. נפריך ע"י
.
- לא נכון. נפריך ע"י
.
- לכל פונקציה
מתקיים ש
, עבור
כלשהם, החל מ
כלשהו. לכן, החל מאותו
, ![{\displaystyle \displaystyle (1+c'')\cdot f(n)\leq f(n)+g(n)\leq (1+c')\cdot f(n),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d5c6d95c0a50ea5abfbe2998f6a6292f19b14ead)
מה שמוכיח את הטענה.
(לפי כללים פשוטים מחדו"א),
ולכן עפ"י כללי הגבולות שראינו, הטענה נכונה.
כללים לגבי מקסימום
[עריכה]
אנא הוכח או הפרך כ"א מהכללים הבאים:
![{\displaystyle \displaystyle f(n)+g(n)=\Theta (\max\{f(n),g(n)\})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/005e6bb0e4e4d838bf4f98444b79a7eb17c4cf78)
![{\displaystyle \displaystyle f(n)-g(n)=\Theta (\max\{f(n),g(n)\})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c40c23cb1a25674f06efc2c42cd78af982efe030)
נשים לב שתמיד מתקיים:
,
.
הטענה, לכן, נכונה.
ניקח
, ו
. קל לראות ש
: הוכחנו בכיתה ש
, ובאותו אופן בדיוק אפשר להראות ש
. הטענה, לכן, איננה נכונה.
ו
הן פונקציות חיוביות ממש,
והגבול
קיים ושווה ל
. אנא הוכח או
הפרך את הטענה הבאה: אם
או
, אז
.
הטענה נכונה.
הוכחה: נניח בשלילה שהטענה מוטעית, ואכן
. עפ"י ההגדרה, לכן, קיימים שני
קבועים
ו
כך שלערכי
גדולים מספיק,
. נחלק ב
(שימו לב שאין צורך להפוך את סימני
), ונקבל
. מכללים ידועים בחדו"א, הוכחנו כעת שגבול המנה (אם הוא קיים) חסום בין
ל
, בסתירה לנתון בשאלה.
באופן דומה למדי, נוכל להוכיח את המשפט הבא:
יחסים בין פולינומים
[עריכה]
פולינומים בעלי מקדמים חיוביים. אנא מצא כלל פשוט לקביעת סדרי הגדילה ביניהם.
נניח ש
פולינום מדרגה
, ו
פולינום מדרגה
. אז:
![{\displaystyle \displaystyle f<g\Rightarrow f(n)=O(g(n))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/83bbe7ae49e8faff47deb9977d741c1b45b4786a)
![{\displaystyle \displaystyle f=g\Rightarrow f(n)=\Theta (g(n))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bbc59295255d0ade4e5355e77b1670580409ffd2)
![{\displaystyle \displaystyle f>g\Rightarrow f(n)=\Omega (g(n))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7cdc691912de787a3483a0333a1b46268f89376b)
במילים אחרות, זה נקבע עפ"י יחס החזקות הגבוהות ביותר. קל להוכיח טענות אלו ע"י כללי הגבולות שראינו.
הכוון השני לכללי הגבולות
[עריכה]
היא פונקציה חיובית ממש, מונוטונית עולה, ושואפת לאינסוף. אנא הוכח שקיימת פונקציה
כך שמתקיים
אבל הגבול
אינו קיים.
נבנה את הפונקציה
כך:
- ראשית נקבע צמדים של נקודות.
- נקבע
, ו
כנקודה הקטנה ביותר בה
(חייבת להיות נקודה כזו, כי
שואפת לאינסוף).
- נקבע
, ו
כנקודה הקטנה ביותר בה
(חייבת להיות נקודה כזו, כי
שואפת לאינסוף).
- נמשיך כך הלאה: נקבע
, ו
כנקודה הקטנה ביותר בה
) (חייבת להיות נקודה כזו, כי
שואפת לאינסוף), וכולי.
- כעת נגדיר את
בעזרת הזוגות:
- עבור
,
;
.
- עבור
,
;
.
- עבור
,
;
. נמשיך כך הלאה והלאה.מהבניה קל לראות את הדברים הבאים:
פונקציה מונוטונית עולה.
- בכל נקודה ונקודה,
נמצאת בין
ל
. לכן
בהכרח.
- יש אינסוף נקודות בהן
, אבל גם אינסוף נקודות בהן
, ולכן לא ייתכן שהגבול
קיים.
הם שני קבועים שלמים גדולים ממש מ1. אנא הוכח שמתקיים
.
היות ש
הם שני קבועים שלמים גדולים ממש מ1, אז
היא פונקציה מונוטונית עולה בתחום המתאים, ונוכל להשתמש
בכלל הראשון של חסמי האינטגרלים. בנוסף, נזכר ש
(עבור
כלשהו). הצבה פשוטה משלימה את ההוכחה.
הפונקציה
נתונה על ידי הנוסחה.
.
אנא הוכח
.
רמז
נסה להוכיח זאת באותו אופן בו הוכחנו
. כלומר:
- הוכח בנפרד חסמי
ו .
- ערוך מניפולציות על איבר הטור הכללי ועל גבולות הסיכום כך שיתקבל איבר טור שאינו תלוי בגבולות הסיכום (ולכן ניתן יהיה להוציאו מחוץ לסכום).
|
נשתמש באותו הרעיון בו השתמשתנו כדי לנתח טור של לוגריתמים.
ראשית נראה כי
.
הוכחה: ![{\displaystyle \displaystyle f(n)=\sum _{i=1}^{n}\sum _{j=i}^{n}[\Theta (j-i+1)]\leq \sum _{i=1}^{n}\sum _{j=1}^{n}[\Theta (n)]=\Theta (n^{3})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cac6eab16c17788f2ba9b67e6545e752060dead8)
.
כעת נראה כי
.
הוכחה:
.
נשים לב שכאשר
בתחום
ו
בתחום
,
אז
.
לכן נקבל
.
.
נשים לב שעבור ערך
כלשהו, נוכל לבצע את החלפת המשתנים
, ונקבל
.
נציב זאת חזרה בסכום הכפול:
.
נבצע החלפת משתנים
, ונקבל:
.
חסם על טור לבניית ערימה בינרית ממערך
[עריכה]
אנא הוכח ש
.
רמז
חלק את הטור לשני טורים; הראשון יהיה טור קצר המכיל מספר קבוע של איברים, והשני יהיה טור ארוך יותר. חסום את הטור השני על ידי טור הנדסי.
|
מצד אחד, כל טור גדול לפחות כמו איברו הראשון. מכאן נקבל:
ולכן הטור המקורי הוא
.
מצד שני, נקבל
,
ולכן נחסום מלמעלה את
.
עבור ערכי
מספיק גדולים,
(קל לראות זאת מל'וספיטל, לדוגמה). נגדיר את
כאינדקס הראשון בו
.
נקבל