זמן בנייה של עץ AVL ממערך בן n איברים לא ממוינים הוא nlogn נכון?
אין מצב לחסם יותר נמוך מכך?
בנייה של עץ AVL
מנהל: TA_Isana
Re: בנייה של עץ AVL
אם אין לך שום הנחה על הקלט, אז זהו החסם הנמוך ביותר
Re: בנייה של עץ AVL
אוקי תודהeliorar כתב:אם אין לך שום הנחה על הקלט, אז זהו החסם הנמוך ביותר
וזמן בנייה סטנדרטי של skiplist זה גם כך או פחות?
Re: בנייה של עץ AVL
פעולת הכנסה של skipList היא O(logn) בממוצע לכן, הכנסת n איברים לרשימת דילוגים תיקח O(nlogn) בממוצע
Re: בנייה של עץ AVL
אוקי תודה שאלה נוספת זה ממבחן 2004eliorar כתב:פעולת הכנסה של skipList היא O(logn) בממוצע לכן, הכנסת n איברים לרשימת דילוגים תיקח O(nlogn) בממוצע
שאלה 3 (25%)
שאלה זו עוסקת בעצי-B
א) (7 נק') שרטט עץ-B בו t=2 (עץ 1,2,3) אשר מכיל את המפתחות A,B,C,D,G,H,K,,M,R,W,Z
ב) (8 נק') שרטט את העץ המתקבל לאחר הוצאה של האיבר G ואחריו M מהעץ.
ג) (5 נק')מהו ערך t במערכת בה גודל מצביע שווה לגודל איבר שווה ל 2 בייט וגודל בלוק הוא 1000 בייט.
ד) (5 נק') במחשב BGU-13 שיכנס לשוק בשנת 2009, מהירות גישה לדיסק תהיה מהירה מאוד (פי 10 איטית יותר מגישה לזיכרון). כיצד תשפיע כניסה זו על שכיחות השימוש בעצי-.B
איך עונים על סעיף ד?
ממה שזכור לי עץ B-tree מקצר זמני גישה לדיסק,אז זה אומר שהשימוש בעצי B-tree יפחת בעקבות השיפור במהירות בזיכרון.
Re: בנייה של עץ AVL
אני חושב כמוך.. השימוש יפחת.
אגב, באותו מבחן איך הוכחת בשאלה 3 (הראשונה חח) זאת עם העץ פורש, את סעיף א'?
אגב, באותו מבחן איך הוכחת בשאלה 3 (הראשונה חח) זאת עם העץ פורש, את סעיף א'?
Re: בנייה של עץ AVL
בשאלה 3 ששם מציגים לך את האלגוריתם של קרוסקל למציאת MSTeliorar כתב:אני חושב כמוך.. השימוש יפחת.
אגב, באותו מבחן איך הוכחת בשאלה 3 (הראשונה חח) זאת עם העץ פורש, את סעיף א'?
דילגתי על זה,לא נראה לי שנצטרך להוכיח נכונות של אלגוריתם במבחן. פעם דרשו מהם הוכחות היום זה יותר תכלס אז זה נראה לי מוזר להתעקב על זה,מה שגם לא זכור לי שהוכיחו לנו את הנכונות של האלגוריתם הזה.
Re: בנייה של עץ AVL
שאלה נוספת (יש הרבה היום )
מישהוא יודע מה זמן הבנייה של עץ B-tree ?
)מישהוא יודע מה זמן הבנייה של עץ B-tree ?
Re: בנייה של עץ AVL
אני מצטט מקורמן:
כלומר עבור n איברים זמן הריצה הוא: (O(n•th) = O(n•t log(tn) - לא סגור על זה ב100%, אשמח אם מישהו מהמתרגלים יאשר את זה..Inserting a key into a B-tree in a single pass down the tree:
We insert a key k into a B-tree T of height h in a single pass down the tree, requiring O(h) disk accesses.
The CPU time required is O(th) = O(t logt n). The B-TREE-INSERT procedure uses B-TREE-SPLIT-CHILD to guarantee that the recursion never descends to a full node.