الگوریتم تصادفی -فصل 2
انتخاب و مرتب سازی
n عدد متمایز و عدد صحیح i بین 1 تا n داده شده است. می خواهیم i-امین عنصر را پیدا کنیم.
راه حل معمولی: یک عدد از مجموعه مثلا اولی را بر می داریم و رتبه آن را حساب کرده و همزمان اعداد را به دو مجموعه بزرگتر و کوچکتر از آن تقسیم می کنیم. اگر i بزرگتر از تعداد اعضای مجموعه ی کوچکتر بود درون آن را می گردیم، در غیر این صورت درون مجموعه ی بزرگتر را برای i منهای تعداد اعضای کوچکتر از عدد فعلی می گردیم.
زمان الگوریتم معمولی: O(n^2)
worst case analysis: T(n)<= T(n-1)+O(n) ==> T(n) = O(n^2)
مجموعه حالت ها: n عدد
پیشامد: i-امین عدد
راه حل 1:
انتخاب تصادفی: یک عدد تصادفی انتخاب می کنیم، نه الزاما اولین عدد.
ایده: مشابه باینری سرچ که با تقسیم و حل زمان را بهبود می دهد، اینجا این تابع تصادفی را برای جستجو داریم.
ایده: از روی سوال قبلی (پیدا کردن میانه) می دانیم که نزدیک وسط بودن خیلی کار ما را راحت تر می کند.
زمان:
Xi: متغیر تصادفی رنک عنصر انتخابی در مرحله i ام الگوریتم
E(T(n)) <= sum_j_1_n( pr(Xi=j)T(max(j,n-j) ) +O(n)
pr(Xi=j) = 1/n
split to close to median & far from median : if j=n/4 ==> max(j,n-j)=3n/4
E(T(n)) <= 1/n*( sum_j_1_n/4(T(n-1))+sum_j_n/4_3n/4(T(3n/4))+sum_j_3n/4(T(n)) )+O(n)
E(T(n)) <= 1/n( n/2*T(n-1)+n/2*T(3n/4))+O(n)
E(T(n)) <= 1/2(T(n-1)+T(3n/4))+O(n)
از شباهت این مساله با مساله پیدا کردن میانه حدس می زنیم جواب آن هم O(n) باشد و با استقرا ثابت می کنیم.
راه حل 2:
ایده: استفاده از تابع میانه به صورت جداگانه
انتخاب تصادفی: از تابع میانه استفاده کنیم و با باینری سرچ آن را به دست بیاوریم.
T(n) = T_find_median(n)+T(n/2)
T_find_median(n) = O(n/delta)
2*delta=1/2 ==> T_find_median = O(n)
=> T(n) = T(n/2)+O(n) ==> T(n)=O(n)
راه حل 3: راه قطعی است که با همین زمان به جواب می رسد!
ایده: غیرتصادفی کردن: روشی ارائه می دهیم که خصوصیت بالا را حفظ کند و تصادفی نباشد.
ابتدا مجموعه را به زیر مجموعه های 5 تایی تقسیم می کنیم بعد در هر کدام میانه را حساب می کنیم و با فراخوانی همین تابع به صورت بازگشتی میانه ی این مجموعه را به دست می آوریم و همراه با به دست آوردن میانه، عمل partitioning هم انجام می دهیم. (مجموعه را به دو قسمت کمتر از میانه و بیشتر از میانه تقسیم می کنیم.)
اثبات: تفاوت این روش با روش قبل این است که اینجا pivot را به صورت رندم انتخاب نمی کنیم که حداکثر می تواند در زمان تاثیر داشته باشد نه درستی، چون در حالت قبل هم که تصادفی انتخاب می کردیم جواب درست همیشه ساخته می شد و فقط زمان متفاوت می شد.
زمان: پیدا کردن میانه یک مجموعه 5 عضوی = O(1)
T(n)<=T(n/5)+O(n)+T(7n/10)
چون هر کدام از مجموعه های partition ها حداکثر 7n/10 عضو دارند. (به دلیل تقسیم های بعدی، n/5/2=n/10 و ceiling(5/2)=3 )
در نهایت زمان T(n) = O(n) به دست می آید.
----------
مرتب سازی:
راه حل 1:
ایده: پیدا کردن میانه
با استفاده از مطالب قسمت قبل (تصادفی معمولی) میانه را پیدا می کنیم، بعد هر کدام از زیر مجموعه ها را بازگشتی مرتب می کنیم، چون قبلا partition کرده بودیم نتیجه مرتب شده است.
زمان: در هر قدم الگوریتم همه ی عناصر را با pivot مقایسه می کنیم و با زمان این مقایسه ها در زیر مساله ها جمع می کنیم. پس زمان کل برابر جمع تعداد مقایسه ها است.
متغیر تصادفی: تعداد عناصر مقایسه شده
حداکثر هر عنصر یک بار با یک عنصر دیگر مقایسه می شود پس متغیرهای تصادفی دیگری به شکل Xij تعریف می کنیم که اگر عناصر i و j مقایسه شوند یک می شوند در غیر این صورت صفر.
اگر i و j در هیچ فراخوانی از تابع مرتب سازی حضور نداشته باشند (زیر مساله ها) مقایسه نمی شوند و Xij=0 خواهد بود. در غیر این صورت تنها در صورتی مقایسه می شوند که یکی از آنها به عنوان pivot انتخاب شود.
pr(Xij=1)=2/(j-i+1)
با جایگذاری به زمان nlogn می رسیم.
راه حل 2:
ایده: استفاده از پیدا کردن میانه با روش تصادفی دوم
T(n) = T(n/4)+T(3n/4)+O(n)
این راه از راه حل قبلی بدتر است، چون کار تکراری انجام می دهیم. (قسمتی که برای میانه 1/4 را چک می کنیم و بعد برای تقسیم کردن دوباره این کار را انجام می دهیم.) اما در کل همان O(nlogn) می شود.
