برزدن فیشر یتس: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
Roodabeh sfv (بحث | مشارکت‌ها) بدون خلاصۀ ویرایش |
Bahmanshams (بحث | مشارکت‌ها) |
||
خط ۱۴۹:
{{سخ}}
الگوریتم فشر یتس زمان غیرضروری‌ای را صرف پیدا کردن k امین عدد خط نخورده می‌کند (خط ۳). داستنفلد برای آن راه حلی ارائه کرد. در هر بار اجرای حلقهٔ دستورات عدد خط خورده را با جابه‌جا کردن آن با آخرین عدد خط نخورده به انتهای آرایه منتقل کنیم. این راه حل پیچیدگی زمانی بر زدن را از
<math>O(n^2)</math>
به
<math>O(n
{{سخ}}
'''۱-'''
| |||