۰
subtitle
ارسال: #۱
چند سوال از الگوریتم selection (مبحث تقسیم و غلبه): میانه میانه ها
سوال اول و دوم از کتاب پوران فصل ۲(تقسیم و غلبه)
۱) در الگوریتم selection (همان الگوریتم بهینه برای یافتن k امین کوچکترین عنصر در آرایه n تایی به کمک میانه میانه ها)آرایه ورودی به گروه های ۵ تایی تقسیم شدند آیا اگر به گروه های ۷ عنصری تقسیم کنیم زمان همچنان خطی است؟ به گروه های ۳ عنصری چطور؟
پاسخ:
فرض کنیم گروه ها k عنصری باشند تعداد اعداد بزرگتر( یا کوچکتر) از میانه میانه ها(x) حداقل
⌈k2⌉(⌈12⌈nk⌉⌉−2)≥n4−k
است، پس در بدترین حالت selection به صورت بازگشتی روی حداکثر
n−(n4−k)=3n4k
عنصر اجرا میشود.
T(n)≤T(⌈nk⌉)T(3n4k)O(n)
تا این جا رو مشکلی ندارم
سوالم از اینجا به بعده :
برای آنکه این رابطه خطی باشد باید T(n)≤cn که با جایگذاری ثابت میشود :
k>4
عدد چطور بدست اومده؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟
تو رابطه میذارم
اما ۴ بدست نمیاد
۲)نشان دهید اگر n≥140 حداقل ⌈n4⌉ عنصر از n بزرگتر و حداقل ⌈n4⌉ عنصر از n کوچکتر است؟
۳) اگر در الگوریتم selection به دسته های ۲k-1 عنصری تقسیم کنیم رابطه T(n) به صورت زیر بدست می آید:
T(n)=θ(n)T(⌈n2k−1⌉)T(3k−22(2k−1))n2k)
T دوم رو متوجه نمیشم.
۴)حداکثر تعداد عناصری که میتوانند در دو طرف میانه میانه ها باشد؟
2(n5)−1
۱) در الگوریتم selection (همان الگوریتم بهینه برای یافتن k امین کوچکترین عنصر در آرایه n تایی به کمک میانه میانه ها)آرایه ورودی به گروه های ۵ تایی تقسیم شدند آیا اگر به گروه های ۷ عنصری تقسیم کنیم زمان همچنان خطی است؟ به گروه های ۳ عنصری چطور؟
پاسخ:
فرض کنیم گروه ها k عنصری باشند تعداد اعداد بزرگتر( یا کوچکتر) از میانه میانه ها(x) حداقل
⌈k2⌉(⌈12⌈nk⌉⌉−2)≥n4−k
است، پس در بدترین حالت selection به صورت بازگشتی روی حداکثر
n−(n4−k)=3n4k
عنصر اجرا میشود.
T(n)≤T(⌈nk⌉)T(3n4k)O(n)
تا این جا رو مشکلی ندارم
سوالم از اینجا به بعده :
برای آنکه این رابطه خطی باشد باید T(n)≤cn که با جایگذاری ثابت میشود :
k>4
عدد چطور بدست اومده؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟
تو رابطه میذارم
اما ۴ بدست نمیاد
۲)نشان دهید اگر n≥140 حداقل ⌈n4⌉ عنصر از n بزرگتر و حداقل ⌈n4⌉ عنصر از n کوچکتر است؟
۳) اگر در الگوریتم selection به دسته های ۲k-1 عنصری تقسیم کنیم رابطه T(n) به صورت زیر بدست می آید:
T(n)=θ(n)T(⌈n2k−1⌉)T(3k−22(2k−1))n2k)
T دوم رو متوجه نمیشم.
۴)حداکثر تعداد عناصری که میتوانند در دو طرف میانه میانه ها باشد؟
2(n5)−1