מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/עצי חיפוש בינריים/תרגילים/זמן הריצה של הפונקציות למעבר על כל הצמתים - הוכח שגויה/שאלה

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



א'[עריכה]

להלן הוכחה שגויה לכך שכל אחת מהפעולות למעבר על כל איברי העץ שראינו Post-Order In-Order, וIn-Order), פועלת בזמן ריבועי במספר האיברים בעץ.


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

(בסיס האינדוקציה) עבור , .

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

T(n) = \Theta(i^2) + \Theta((n - i)^2)

ב'[עריכה]

מה בעייתי בהוכחה הבאה לכך שזמן הריצה הוא לינארי?