۰
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