الگوريتم كوئيك سورت

[taher64]

اگه در الگوريتم كوئيك سورت به جاي شروع از ايتم اول (low) از ايتم اخر (high) يا وسط (mid) شروع كنيم پيچيدگي ما چند مي شود ؟

[mortezamsp]

اگه عنصر محوری اول یا آخر باشه پیچیدگی میشه n² و اگه عنصر محوری وسط باشه پیچیدگی میشه nlogⁿ چون باید هربار آرایه نصف بشه و در هر بار نصف شدن یک جست و جو از مرتبه n انجام بشه.

[somayeh _masaeli]

در بدترترین حالت همان
n2

[FastCode]

سه شنبه 26 آبان 1388, 13:54 عصر

شنبه 24 بهمن 1388, 20:41 عصر
دوست عزیز من به شما قول میدم که taher64)OP) تا این لحظه merge-sort و heap-sort رو هم implement کردن.

[newamir]

کوئیک سورت همواره در بدترین حالت پیچیدگی n2 دارد ولی امید ریاضی زمان اجرای آن (n*log(n است. اگر منظور شما از آیتم اول آیتم مینیمم، و آیتم آخر آیتم ماکزیمم، mortezamsp درست گفته اند. ولی اگر منظورتان از اول و آخر و وسط، مکان آیتم انتخاب شده است، این موضوع هیچ تاثیری بر زمان اجرا نخواهد گذاشت.