۰
subtitle
ارسال: #۱
  
تعداد مقایسه های لازم برای لیستی با n عنصر؟
با سلام .
مرتب سازی n عنصر حداکثر به چند مقایسه نیاز دارد؟
تو clrs مطلبی گفته شده که در روش های مرتب سازی با استفاده از روش مقایسه عناصر مرتبه زمانی حداقل از مرتبه nlogn خواهد بود.با این نکته که جواب نداد.چون برای ۵ عنصر جواب صحیح عدد ۷ میباشد.
مرتب سازی n عنصر حداکثر به چند مقایسه نیاز دارد؟
تو clrs مطلبی گفته شده که در روش های مرتب سازی با استفاده از روش مقایسه عناصر مرتبه زمانی حداقل از مرتبه nlogn خواهد بود.با این نکته که جواب نداد.چون برای ۵ عنصر جواب صحیح عدد ۷ میباشد.
۰
ارسال: #۲
  
RE: تعداد مقایسه های لازم برای لیستی با n عنصر؟
مگه نمیگید حداکثر؟
خب اگه ۵ تا عنصر داشته باشیم، حداکثر ۱۰ مقایسه لازم است:
فرض کنید ورودی ۵،۴،۳،۲،۱ رو بدیم به Insertion Sort؛ اون وقت ۴ با ۱ عنصر، ۳ با ۲ تا، ۲ با ۳ تا و ۱ با ۴ عنصر مقایسه میشه پس میشه ۱۰ مقایسه! و ۵log5 هم میشه ۱۰!
خب اگه ۵ تا عنصر داشته باشیم، حداکثر ۱۰ مقایسه لازم است:
فرض کنید ورودی ۵،۴،۳،۲،۱ رو بدیم به Insertion Sort؛ اون وقت ۴ با ۱ عنصر، ۳ با ۲ تا، ۲ با ۳ تا و ۱ با ۴ عنصر مقایسه میشه پس میشه ۱۰ مقایسه! و ۵log5 هم میشه ۱۰!
۰
ارسال: #۳
  
RE: تعداد مقایسه های لازم برای لیستی با n عنصر؟
اگر جواب به ازای ۵ برابر ۷ میشده،حتما منظور حداقل تعداد مقایسه بوده که ثابت میشه برابر است با:
[tex]\left \lceil lg(n!) \right \rceil[/tex]
[tex]\left \lceil lg(n!) \right \rceil[/tex]
موضوعهای مرتبط با این موضوع... |
|||||
موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
تعداد برگ درخت؟؟؟؟؟؟؟ | rad.bahar | ۴ | ۴,۰۱۳ |
۱۵ آذر ۱۴۰۲ ۱۱:۵۳ ق.ظ آخرین ارسال: mohamadrra |
|
تعداد جواب | mostafaheydar1370 | ۲۱ | ۱۷,۵۱۸ |
۰۱ مهر ۱۳۹۹ ۱۱:۴۱ ب.ظ آخرین ارسال: miinaa |
|
تعداد روش های نوشتن عدد n | ss311 | ۲ | ۳,۰۶۲ |
۱۳ بهمن ۱۳۹۸ ۰۵:۲۷ ب.ظ آخرین ارسال: ss311 |
|
تعداد مسیرها در گراف | ss311 | ۰ | ۱,۸۴۸ |
۰۸ بهمن ۱۳۹۸ ۱۲:۴۷ ب.ظ آخرین ارسال: ss311 |
|
تعداد درخت فراگیر | ss311 | ۰ | ۲,۱۲۶ |
۰۶ بهمن ۱۳۹۸ ۰۵:۰۶ ب.ظ آخرین ارسال: ss311 |
|
تعداد توابع پوشا | ss311 | ۰ | ۱,۸۹۳ |
۰۶ بهمن ۱۳۹۸ ۰۴:۵۷ ب.ظ آخرین ارسال: ss311 |
|
تعداد اعداد ۵ رقمی هم ارز | ss311 | ۲ | ۲,۴۰۷ |
۰۶ بهمن ۱۳۹۸ ۰۴:۳۹ ب.ظ آخرین ارسال: ss311 |
|
تعداد رشته های n بیتی | hamedsos | ۲ | ۲,۷۷۷ |
۱۸ آبان ۱۳۹۸ ۰۹:۰۶ ب.ظ آخرین ارسال: Jooybari |
|
مقایسه دانشگاه ها | imali | ۲ | ۲,۸۷۱ |
۰۵ مهر ۱۳۹۸ ۱۲:۲۵ ق.ظ آخرین ارسال: imali |
|
رتبه لازم برای قبولی داده کاوی امیرکبیر | dataloverz | ۵ | ۴,۴۸۷ |
۳۱ خرداد ۱۳۹۸ ۱۲:۳۱ ق.ظ آخرین ارسال: dataloverz |
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close