۰
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