نمايش پست تنها
قديمي ۱۱-۹-۱۳۹۱, ۰۹:۲۲ قبل از ظهر   #116 (لینک دائم)
narssic Female
عضو فعال
 
آواتار narssic
 
تاريخ عضويت: دي ۱۳۹۰
محل سكونت: تهران
پست ها: 18
تشكرها: 1
7 تشكر در 6 پست
My Mood: Badhal
پيش فرض

نقل قول:
نوشته اصلي بوسيله mardin200 نمايش پست
سوال 14 : مرتب سازي سريع زماني از مرتبه n^2 است كه داده ها از قبل مرتب باشند (صعودي يا نزولي) البته به شرطي كه در هر مرحله عنصر اول كليد فرض شود.
اگر n‌ عدد متمايز داشته باشيم با !n ترتيب مختلف مي توانند قرار بگيرند كه از اين !n فقط دو حالتش ظاهرا از مرتبه n^2 خواهند بود ولي اگر مثلا اگر همه مرتب باشند به غير از عنصر اول و دوم و يا براي حالات مشابه ديگر چي؟؟؟
سوال 14 دقیقا از کتاب دکتر قدسی اومده، صفحه 22 سوال 25.2
جواب در صفحه 196:
اگر در هر مرحله، الگوریتم مرتب سازی سریع تصادفی بزرگترین (یا کوچکترین) عنصر را بعنوان محور انتخاب کند، در آن صورت این الگوریتم مانند مرتب سازی سریع قطعی بر روی آرایه ای مرتب است که در زمان O(n^2) این کار را انجام می دهد احتمال این که چنین حالتی پیش بیاید برابر است با 1/(n^2) - یک روی n بتوان 2-
narssic آفلاين است   پاسخ با نقل قول
از narssic تشكر كرده است:
mahdiii (۱۱-۹-۱۳۹۱)