۰
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