למה מיון מהיר זה nlogn

[member2006]

למה מיון מהיר זה nlogn

אני לא מדברת על המקרה הגרוע אלא בממוצע

בהתחלה ה partition זה n
אחכ זה פעמיים n/2
אחכ 4 פעמים n/4

וכו.. והסכום זה n בריבוע

 

[mazory]

צייר את עץ החלוקה

שמתפצל כל פעם לשניים.

סך הפעולות שצריך לבצע בכל רמה הוא O של N.

עומק העץ הוא log zz ולכן סך הפעולות הוא nLogn.