Часові складності всіх алгоритмів сортування
Ефективність алгоритму залежить від двох параметрів:
- Часова складність
- Космічна складність
Часова складність:
Часова складність визначається як кількість разів, коли певний набір інструкцій виконується, а не загальний витрачений час. Це тому, що загальний час також залежить від деяких зовнішніх факторів, таких як використовуваний компілятор, швидкість процесора тощо.
Космічна складність:
Складність простору - це загальний простір пам'яті, необхідний програмі для її виконання.
Обидва обчислюються як функція вхідного розміру (n). Тут важливо те, що незважаючи на ці параметри, ефективність алгоритму також залежить від природи і розмір в введення.
Типи складності часу:
- Найкраща складність часу: Визначте вхід, для якого алгоритм займає менше часу або мінімальний час. У найкращому випадку обчислити нижню межу алгоритму. Приклад: у лінійному пошуку, коли дані пошуку присутні в першому місці великих даних, тоді відбувається найкращий випадок.
- Середня складність часу: У середньому випадку взяти всі випадкові вхідні дані та обчислити час обчислення для всіх вхідних даних.
А потім ділимо це на загальну кількість входів. - Найгірша складність часу: Визначте вхідні дані, для яких алгоритм займає тривалий або максимальний час. У гіршому випадку обчислюють верхню межу алгоритму. Приклад: у лінійному пошуку, коли дані пошуку присутні в останньому місці великих даних, виникає найгірший випадок.
Нижче наведено аркуш швидкого перегляду, до якого ви можете звернутися в останню хвилину:
| Алгоритм | Часова складність | Космічна складність | ||
|---|---|---|---|---|
| Найкращий | Середній | Найгірше | Найгірше | |
| Сортування вибору | O(n 2 ) | O(n 2 ) | O(n 2 ) | О(1) |
| Бульбашкове сортування | O(n) | O(n 2 ) | O(n 2 ) | О(1) |
| Сортування вставкою | O(n) | O(n 2 ) | O(n 2 ) | О(1) |
| Сортування купи | O(n log(n)) | O(n log(n)) | O(n log(n)) | О(1) |
| Швидке сортування | O(n log(n)) | O(nlog(n)) | O(n 2 ) | O(n) |
| Сортування злиттям | O(nlog(n)) | O(nlog(n)) | O(n log(n)) | O(n) |
| Відро сортування | O(n +k) | O(n +k) | O(n 2 ) | O(n) |
| Сортування Radix | O(nk) | O(nk) | O(nk) | O(n + k) |
| Сортування за кількістю | O(n +k) | O(n +k) | O(n +k) | стрілка) |
| Сортування оболонки | O(n log(n)) | O(n log(n)) | O(n 2 ) | О(1) |
| Тім Сорт | O(n) | O(n log(n)) | O(nlog(n)) | O(n) |
| Сортування дерева | O(n log(n)) | O(nlog(n)) | O(n 2 ) | O(n) |
| Сортування куба | O(n) | O(n log(n)) | O(n log(n)) | O(n) |
Також дивіться:
- Пошук і сортування статей
- Запитання GATE про сортування попереднього року
- Часова та просторова складність сортування вставкою
- Часова та просторова складність сортування відбору
- Часова та просторова складність бульбашкового сортування
- Часова та просторова складність швидкого сортування
- Часова та просторова складність сортування злиттям
- Часова та просторова складність алгоритму сортування Radix
