מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/נוסחאות נסיגה/תרגילים

נוסחת נסיגה עם שורש

עריכה

שאלה

עריכה

בנוסחת הנסיגה  ,‏   מתארת את זמן הריצה של אלגוריתם כלשהו. אנא פתור את הנוסחה.


תשובה

עריכה

נשתמש בפרישה.בעץ המתאים לנוסחה:

  1. צומת הראש מציין את  , והרמה הראשונה תורמת  .
  2. ברמה הבאה, הצומת מציין את  , והרמה תורמת  .
  3. ברמה הבאה אחריה, הצומת מציין את  , והרמה תורמת  .

החוקיות איננה מסובכת, ונוכל להוכיח את הטענה הבאה באינדוקציה פשוטה: ברמה ה  (כאשר ראש העץ נחשב ברמה ה0), הצומת מציין את  , והרמה תורמת  .

כדי למצוא את גובה העץ,  , נפתור  :  
 
 
 
 
כאמור, הרמה ה  תורמת  . נותר, לכן, לסכם את  :  
 
 
 


נוסחת נסיגה לבעיית "דג הסלמון"

עריכה

שאלה

עריכה

  מתארת את זמן הריצה של אלגוריתם כלשהו. אנא הוכח שאם   אז  .


 

כדאי לדעת:

נצטרך את פתרונה של נוסחת נסיגה זו בבעיית "דג הסלמון".


תשובה

עריכה

הוכחה: נוכיח באינדוקציה שקיים   כך ש .

(מעבר האינדוקציה) נניח שהטענה נכונה עד (כולל)  , ונוכיח שהיא נכונה ל .‏ עפ"י נוסחת הנסיגה,  
עבור   כלשהו. לכן, עפ"י הנחת האינדוקציה,  .
עפ"י הנוסחה לטור הנדסי,

 
 
 
 
אם ניקח  ,‏ אז הביטוי האחרון גדול מ .


(בסיס האינדוקציה) היות ש ,‏ אז  ,‏ עבור   כלשהו. נפתור  ,‏ ונקבל  .‏

האינדוקציה, לכן, נכונה עבור  , החל מ .

 


נוסחת נסיגה לאיחוד קבוצות זרות על פי גודל

עריכה

שאלה

עריכה

אנא הוכחה את המשפט הבא:



משפט:

פתרון  
הוא  
.


 

כדאי לדעת:

נצטרך את פתרונה של בעיה זו כשנדבר על מבני נתונים לקבוצות זרות.

תשובה

עריכה

נוכיח באינדוקציה שקיים   כך ש(עבור  -ים מספיק גדולים)  .

(מעבר האינדוקציה) עפ"י נוסחת הנסיגה והנחת האינדוקציה,

 
 
עבור קבוע   כלשהו.

נגזור את הביטוי שבתוך ה , ונקבל  

נגזור את הביטוי פעם שניה, ונקבל ביטוי חיובי. מכאן ברור שמקסימום הביטוי הוא כאשר .

כאשר , אז

 
 
 

(בסיס האינדוקציה) נפתור:  
ונווכח שהדבר נכון עבור   גדול מספיק.

נוסחות נסיגה פשוטות

עריכה

שאלה

עריכה

  מתארת את זמן הריצה של אלגוריתם כלשהו.

  1. אנא הוכח שפתרון נוסחת הנסיגה   הוא  .
  2. אנא הוכח שפתרון נוסחת הנסיגה   הוא  .


הנחיות

להלן הנחיות לסעיף הראשון:

  1. אנא הסבר מדוע מותר לקבוע ש  עבור קבוע   כלשהו.
  2. נניח שקיים קבוע   כך שלכל   מתקיים ‎ . אנא הסבר מדוע בהכרח  . אנא מצא תנאי על   כך שבהכרח נובע מכך כי  .
  3. אנא הסבר מדוע מהאמור עד כה נובע שבהכרח  .
  4. נניח שקיים קבוע   כך שלכל   מתקיים ‎ . אנא הסבר מדוע בהכרח  . אנא הסבר מה התנאי על   כך שינבע מכך כי  .
  5. אנא הסבר מדוע מהאמור עד כה נובע שבהכרח  .
  6. אנא הסבר מדוע מהאמור עד כה נובע שבהכרח  .

תשובה

עריכה

כרגיל, מותר לנו לקבוע ש  עבור קבוע   כלשהו, וזאת משום ש  מתארת את זמן הריצה של אלגוריתם.


נוכיח ש‎‎ . ליתר דיוק, נוכיח באינדוקציה שקיים   כך ש  .


הוכחה: (בסיס האינדוקציה) עבור  , נקבל  , כלומר כל שצריך הוא לבחור   המקיים  .

(מעבר האינדוקציה) נניח שהטענה נכונה עד (כולל)  , ונוכיח שהיא נכונה עד (כולל)  . מהצבה בנוסחת הנסיגה, נקבל  
עבור  , נקבל  .


לסיכום, עבור  , הן בסיס האינדוקציה והן מעבר האינדוקציה מתקיימים.

 

נוכיח ש‎‎ . ליתר דיוק, נוכיח באינדוקציה שקיים   כך ש  .


הוכחה: (בסיס האינדוקציה) עבור  , נקבל  , כלומר כל שצריך הוא לבחור   המקיים  .

(מעבר האינדוקציה) נניח שהטענה נכונה עד (כולל)  , ונוכיח שהיא נכונה עד (כולל)  . מהצבה בנוסחת הנסיגה, נקבל  
עבור  , נקבל  .


לסיכום, עבור  , הן בסיס האינדוקציה והן מעבר האינדוקציה מתקיימים.

 

עלינו להוכיח שפתרון נוסחת הנסיגה   הוא  . אפשר לעשות זאת בכסעיף הקודם, אך נבחר לעשות זאת (שרירותית) בדדוקציה. נרשום  
 

חסמים עליונים ותחתונים למספר נוסחאות נסיגה

עריכה

שאלה

עריכה

אנא מצא חסמים עליונים ותחתונים (כלומר, מסוג   ו ) טובים ככל האפשר לפונקציה   בכל אחד מהסעיפים הבאים. (  מתארת את זמן הריצה של אלגוריתם כלשהו.)

  1.  .‏
  2.  .‏
  3.  , כאשר   הוא קבוע כלשהו.‏

תשובה

עריכה

 , עפ"י מקרה 1 של משפט המאסטר.

נפרוש את הנוסחה:  
 
 
 
 
 
 
(את המעבר האחרון ראינו בטורים שימושיים.)

נגדיר  . בלי הגבלת הכלליות, נניח ש . להלן עץ הפרישה המתקבל:

 
עץ הפרישה.

בעץ זה, לכל אחד מהצמתים המצויירים שני ילדים: אם הצומת מתאים לגודל  , אז הילד השמאלי מתאים ל ,‏ והימני מתאים ל ,‏. מכאן אפשר לראות שמסלולים שמאליים בעץ קצרים יותר ממסלולים ימניים, כי  .‏ לא כל הרמות בעץ מלאות, אם כן, מה שמקשה מעט על ניתוח הסיבוכיות. נגדיר כ  את אורך המסלול השמאלי ביותר, וכ  את אורך המסלול הימני ביותר.

קל לראות שכל רמה מלאה בעץ תורמת  .‏ הרמה הראשונה תורמת  ;‏ הרמה השניה תורמת  ,‏ הרמה השלישית תורמת  ;‏ וכו'.‏ (אפשר להראות זאת פורמאלית באינדוקציה.)

אפשר לראות, לכן, ש  חסומה מלמטה ע"י  , וחסומה מלמעלה ע"י  . אבל היות ש  וכן  , אז  .

נוסחת נסיגה שאיננה מתאימה למשפט המאסטר

עריכה

שאלה

עריכה

  מתארת את זמן הריצה של אלגוריתם כלשהו, והיא פתרונה של נוסחת הנסיגה  .‏ בנוסחה זו,   מספר שלם גדול ממש מ1,   מספר גדול ממש מ1, ו  היא פונקציה המקיימת  , עבור   שלם גדול ממש מ1. אנא הוכח  .

תשובה

עריכה

נשתמש בעץ פרישה. ברמה הראשונה יש צומת יחיד, והוא תורם  . ברמה השניה יש   צמתים, וכל אחד מהם תורם  . ברמה ה  (בהנחה שהרמה הראשונה היא ב ), יש   צמתים, וכל אחד מהם תורם  . אנו יודעים שגובה העץ הוא  . נפשט:  
 
 
 
 
 
 
נשים לב שעפ"י חסמי האינטגרלים לטורים,‏  .

נוסחת נסיגה קלה

עריכה

שאלה

עריכה

מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/נוסחאות נסיגה/תרגילים/נוסחת נסיגה קלה/שאלה

תשובה

עריכה

מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/נוסחאות נסיגה/תרגילים/נוסחת נסיגה קלה/תשובה

נוסחת נסיגה מנחוסה

עריכה

שאלה

עריכה

מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/נוסחאות נסיגה/תרגילים/נוסחת נסיגה מנחוסה/שאלה

תשובה

עריכה

מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/נוסחאות נסיגה/תרגילים/נוסחת נסיגה מנחוסה/תשובה