Алгоритми та структури даних · Middle · Запитання 7 з 75
Чому жодне сортування порівняннями не може бути швидшим за O(n log n) у найгіршому разі?
- 1Сортування завжди копіює весь масив log n разів
- ✓Правильна відповідь: Воно має розрізнити n! порядків: log(n!) ≈ n log n
- 3Кожне порівняння займає O(log n) часу в пам'яті
Пояснення
Кожне порівняння має два результати, тож k порівнянь розрізняють щонайбільше 2ᵏ порядків. Щоб визначити один із n! порядків, потрібно log₂(n!) порівнянь, а це Θ(n log n).