۰
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