۰
subtitle
ارسال: #۱
  
تعداد مقایسه در یافتن دومین کوچکترین عنصر
سلام.
چرا گزینه یک درسته؟
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
چرا گزینه یک درسته؟
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
۲
ارسال: #۲
  
RE: تعداد مقایسه در یافتن دومین کوچکترین عنصر
(۱۴ اردیبهشت ۱۳۹۲ ۱۰:۱۸ ب.ظ)Arshad92 نوشته شده توسط: سلام.
چرا گزینه یک درسته؟
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
سلام
تعداد n-1 مقایسه برای پیدا کردن اولین کوچکترین لازمه. دومین کوچکترین عنصر، در واقع عنصری هست که در مقایسه با کوچکترین عنصر حذف شده(منظورم تو درخت تورنومنت هست). تعداد این عنصرها حداکثر [tex]\left \lceil log n \right \rceil[/tex] تا هست که باید بین اونا مقایسه انجام بگیره که [tex]\left \lceil logn \right \rceil-1[/tex] تا میشه در بدترین حالت. مجموع همه مقایسه ها میشه همون گزینه۱/
۱
ارسال: #۳
  
RE: تعداد مقایسه در یافتن دومین کوچکترین عنصر
برای پیدا کردن دومین کوچکترین عنصر در این روش اومده از الگوریتم تورنومنت استفاده کرده.توضیحی در مورد این روش می دم:
روش تورنومنت یا همون مسابقات حذفی که هر بار دوعدد باهم مقایسه میشوند و اونی که بزرگ تر هست(در این مثال اونی که کوچک تر هست) بالا می آید. در کل برای 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] برابر هست با تعداد دور مسابقات.
روش تورنومنت یا همون مسابقات حذفی که هر بار دوعدد باهم مقایسه میشوند و اونی که بزرگ تر هست(در این مثال اونی که کوچک تر هست) بالا می آید. در کل برای 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] برابر هست با تعداد دور مسابقات.
موضوعهای مرتبط با این موضوع... |
|||||
| موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
| تعداد برگ درخت؟؟؟؟؟؟؟ | rad.bahar | ۴ | ۶,۸۴۵ |
۱۵ آذر ۱۴۰۲ ۱۱:۵۳ ق.ظ آخرین ارسال: mohamadrra |
|
| تعداد جواب | mostafaheydar1370 | ۲۱ | ۲۶,۶۲۰ |
۰۱ مهر ۱۳۹۹ ۱۱:۴۱ ب.ظ آخرین ارسال: miinaa |
|
| تعداد روش های نوشتن عدد n | ss311 | ۲ | ۴,۴۴۴ |
۱۳ بهمن ۱۳۹۸ ۰۵:۲۷ ب.ظ آخرین ارسال: ss311 |
|
| تعداد مسیرها در گراف | ss311 | ۰ | ۲,۶۶۸ |
۰۸ بهمن ۱۳۹۸ ۱۲:۴۷ ب.ظ آخرین ارسال: ss311 |
|
| تعداد درخت فراگیر | ss311 | ۰ | ۳,۰۲۵ |
۰۶ بهمن ۱۳۹۸ ۰۵:۰۶ ب.ظ آخرین ارسال: ss311 |
|
| تعداد توابع پوشا | ss311 | ۰ | ۲,۸۱۳ |
۰۶ بهمن ۱۳۹۸ ۰۴:۵۷ ب.ظ آخرین ارسال: ss311 |
|
| تعداد اعداد ۵ رقمی هم ارز | ss311 | ۲ | ۳,۵۸۱ |
۰۶ بهمن ۱۳۹۸ ۰۴:۳۹ ب.ظ آخرین ارسال: ss311 |
|
| مرتبه زمانی یافتن قطر | Sepideh96 | ۲ | ۴,۹۴۴ |
۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ آخرین ارسال: erfan30 |
|
| تعداد رشته های n بیتی | hamedsos | ۲ | ۴,۰۳۰ |
۱۸ آبان ۱۳۹۸ ۰۹:۰۶ ب.ظ آخرین ارسال: Jooybari |
|
| مقایسه دانشگاه ها | imali | ۲ | ۴,۲۳۶ |
۰۵ مهر ۱۳۹۸ ۱۲:۲۵ ق.ظ آخرین ارسال: imali |
|
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close
