زمان کنونی: ۰۴ دى ۱۴۰۳, ۰۷:۱۷ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

تعداد مقایسه در یافتن دومین کوچکترین عنصر

ارسال:
  

Donna پرسیده:

تعداد مقایسه در یافتن دومین کوچکترین عنصر

سلام.

چرا گزینه یک درسته؟


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
نقل قول این ارسال در یک پاسخ

۲
ارسال:
  

Farid_Feyzi پاسخ داده:

RE: تعداد مقایسه در یافتن دومین کوچکترین عنصر

(۱۴ اردیبهشت ۱۳۹۲ ۱۰:۱۸ ب.ظ)Arshad92 نوشته شده توسط:  سلام.

چرا گزینه یک درسته؟


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

سلام
تعداد n-1 مقایسه برای پیدا کردن اولین کوچکترین لازمه. دومین کوچکترین عنصر، در واقع عنصری هست که در مقایسه با کوچکترین عنصر حذف شده(منظورم تو درخت تورنومنت هست). تعداد این عنصرها حداکثر [tex]\left \lceil log n \right \rceil[/tex] تا هست که باید بین اونا مقایسه انجام بگیره که [tex]\left \lceil logn \right \rceil-1[/tex] تا میشه در بدترین حالت. مجموع همه مقایسه ها میشه همون گزینه۱/
نقل قول این ارسال در یک پاسخ

۱
ارسال:
  

azad_ahmadi پاسخ داده:

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] برابر هست با تعداد دور مسابقات.
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تعداد برگ درخت؟؟؟؟؟؟؟ 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?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close