سلام.
چرا گزینه یک درسته؟
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
(۱۴ اردیبهشت ۱۳۹۲ ۱۰:۱۸ ب.ظ)Arshad92 نوشته شده توسط: سلام.
چرا گزینه یک درسته؟
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
سلام
تعداد n-1 مقایسه برای پیدا کردن اولین کوچکترین لازمه. دومین کوچکترین عنصر، در واقع عنصری هست که در مقایسه با کوچکترین عنصر حذف شده(منظورم تو درخت تورنومنت هست). تعداد این عنصرها حداکثر [tex]\left \lceil log n \right \rceil[/tex] تا هست که باید بین اونا مقایسه انجام بگیره که [tex]\left \lceil logn \right \rceil-1[/tex] تا میشه در بدترین حالت. مجموع همه مقایسه ها میشه همون گزینه۱/
برای پیدا کردن دومین کوچکترین عنصر در این روش اومده از الگوریتم تورنومنت استفاده کرده.توضیحی در مورد این روش می دم:
روش تورنومنت یا همون مسابقات حذفی که هر بار دوعدد باهم مقایسه میشوند و اونی که بزرگ تر هست(در این مثال اونی که کوچک تر هست) بالا می آید. در کل برای n عدد [tex]\left \lceil Log{_{2}}^{n} \right \rceil[/tex] دور و [tex](n-1)[/tex] مسابقه لازم است. برای یافتن کوچیک ترین کلید، کلید هایی که به کوچک ترین کلید باخته اند کوچکترین رو انتخاب می کنیم. این عمل به [tex]\left \lceil Log{_{2}}^{n} \right \rceil - 1[/tex] زمان نیاز دارد.
پس کل تعداد مقایسه ها بصورت :
[tex]T(n) = (n-1) \left \lceil Log{_{2}}^{n} \right \rceil - 1[/tex]
[tex](n-1)[/tex] برابر هست با تعداد یافتن کوچک ترین کلید
[tex]\left \lceil Log{_{2}}^{n} \right \rceil - 1[/tex] برابر هست با تعداد دور مسابقات.