سلام
سوال ۹۵ فصل اول کتاب طراحی الگوریتم پوران رو میشه یکی برا من توضیح بده که چطور گزینه ۲ شده؟
من فکر میکنم باید گزینه ۳ باشه، جواب تشریحی هم نداره برا همین نمیدونم که قضیه چیه!!!
ممنون میشم اگر کمکم کنین
پ.ن: این سوال، یکی از سوالات علوم کامپیوتر سال ۸۴ بوده
صورت سوال رو اگر می تونید بذارید
صورت سوال پر از الگوریتم و کد و مرتبه و اینجور چیزاست!
اگر امکانش باشه، برای اینکه اشتباه تایپی هم ایجاد نشه از روی کتاب بخونین و جواب بدین خیلی ممنون میشم
(۳۰ تیر ۱۳۹۱ ۱۲:۳۶ ق.ظ)MSZ نوشته شده توسط: صورت سوال پر از الگوریتم و کد و مرتبه و اینجور چیزاست!خوب اگه کتاب رو داشتم دیگه نمیگفتم صورت سوال رو بذاری که.
اگر امکانش باشه، برای اینکه اشتباه تایپی هم ایجاد نشه از روی کتاب بخونین و جواب بدین خیلی ممنون میشم
پ.ن : عکس بگیر برادر، تایپ نکن
عکس روی سوال رو آپلود کردم.
به نظرم گزینه ۳ درست باشه. یکم کدش پیچیدست.
من اینطوری حلش کردم. نمیدونم درسته یا نه؟
برای اینکه بدترین حالت اتفاق بیفته باید حلقه while بیشترین تکرارو داشته باشه و موقعی این اتفاق میفته که نه break دوم اجرا بشه و نه دستور c++
اگه فرض کنیم همه عناصر آرایه مشابه باشن، در اینصورت حتما این دو حالت رخ میده. در اینصورت میشه به جز دو دستور
c=2p+1 و p=c بقیه دستورهای تخصیص رو حذف کرد. چون دیگه تاثیری در تعداد اجرا ندارن.
بنابراین تعداد دفعات اجرای while وابسته به مقدار c میشه که داره از ۱ شروع میشه و هربار دوبرابر. یعنی تا logn حداکثر بیشتر نمیره.
بطور دقیقتر میشه با یه آرایه ۱۶ تایی که همه خونه هاش مساوین امتحان کرد:
به ازای i=15,14,...,8 حلقه while چهار بار اجرا میشه. یعنی ۱۶/۲ بار به تعداد log16 (سقف)
به ازای i=7,6,5,4 حلقه while سه بار اجرا میشه. یعنی ۱۶/۴ بار به تعداد log16-1
به ازای i=3,2 حلقه while دو بار اجرا میشه یا ۱۶/۸ بار به تعداد log16-2
و به ازای i=1 حلقه یکبار اجرا میشه یا ۱۶/۱۶ بار به تعداد log16-3
به طور کلی میشه:
[tex]\frac{n}{2}[log n] \frac{n}{2^{2}}[logn-1] \frac{n}{2^{3}}[logn-2] ... \frac{n}{2^{k}}[logn-(k-1)]\\ =n[\frac{1}{2}logn (\frac{1}{2^{2}}logn-\frac{1}{2^{2}}) (\frac{1}{2^{3}}logn-\frac{2}{2^{3}}) ... (\frac{1}{2^{k}}logn-\frac{k-1}{2^{k}})]\\ =n.logn(\frac{1}{2} \frac{1}{2^{2}} ... \frac{1}{2^{k}})-n[\sum_{i=1}^{k}\frac{i-1}{2^{i}}][/tex]
که k=logn و قسمت اول خط آخر میشه [tex]O(nlogn)[/tex] و قسمت دوم هم از [tex]O(n)[/tex]
(جواب اون سیگما میشه [tex]1-\frac{logn 1}{n-1}[/tex])
که جمعش میشه گزینه ۳