۰
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