سلام.
دوستان آیا این سوال درست است یا نه؟
اگر ممکنه دلیلتون رو بفرمایید:
اگر در الگوریتم Insertion-Sort آرایه را ابتدا به صورت تصادفی بُر بزنیم، در این صورت زمان اجرای الگوریتم از O(nlogn می‌شود
آیا درسته؟
بُر زدن که همان Shuffle است، دقیقاً یعنی چی کار؟
درست نیست. در صورت بر زدن الگوریتم مرتب‌سازی درجی از مرتبه‌ی تتای n^2 خواهد بود.
اگر قبل از اجرای الگوریتم عناصر آرایه رو به صورت تصادفی با هم جابجا کنیم بطوریکه احتمال وقوع هر جایگشتی از این اعداد یکسان باشه اونوقت به این کار میگن randomized کردن الگوریتم. این کار یه جورایی میشه همون بر زدن.
تشکر
خیلی لطف کردید
یعنی در بهترین حالت هم دیگه از تتای n نیست؟ میتونه تتای n باشه درست میگم؟
به احتمال [tex]\frac{1}{n!}[/tex]
(۱۸ دى ۱۳۹۲ ۱۲:۲۶ ق.ظ)mahmood1 نوشته شده توسط: یعنی در بهترین حالت هم دیگه از تتای n نیست؟ میتونه تتای n باشه درست میگم؟مرتب‌سازی درجی در بهترین حالت از مرتبه‌ی تتای n و در بدترین حالت از مرتبه‌ی تتای n^2 هستش.
عمل بر زدن تاثیری تو درستی جمله‌ی بالا نداره. جمله‌ی بالا در شرایط کلی همیشه درسته.