Пояснення часової та просторової складності алгоритму
Уявіть собі дві програми, які виконують абсолютно однакову роботу. Здайте кожній тисячу записів, і ви не зможете їх відрізнити. Однак, здайте їм мільярд, і одна завершить роботу, перш ніж ви відпустите клавішу Enter, поки інша все ще працює наступного вівторка.
Той самий ноутбук. Ті самі дані. Різниця між ними полягає в часовій складності, яка є лише назвою того, наскільки швидко зростає робоче навантаження алгоритму, коли ви передаєте йому більше вхідних даних.
Ми розглянемо, що насправді означає цей термін, як його записує нотація Big O, як це розібратися з реального фрагмента коду та де з'являється просторова складність. Потім, наприкінці, місце, де все це перестає бути домашнім завданням і починає коштувати реальних грошей: смарт-контракти.
Що таке часова складність алгоритму?
Забудьте на мить про секунди. Часова складність враховує кроки. Порівняння, присвоєння значень, трохи арифметики тут і там, і ви записуєте загальну суму як функцію від n, що є розміром вхідних даних.
Ось про найнуднішу функцію, яку тільки можна уявити:
python def print_all(items): для елемента в елементах: print(item)
Десять елементів? Десять проходів циклу. Десять тисяч? Десять тисяч проходів.
Робота піднімається по прямій лінії поруч із вхідними даними, тому ми називаємо її O(n).
Можливо, кожна поїздка справді коштує трьох невеликих операцій замість однієї. Гаразд, це 3n. Нікого це не хвилює, чесно кажучи, бо подвоєння списку все одно подвоює роботу, а ця крива зростання — це саме те, що нам потрібно. Точне число навмисно викидається.
Ось чому кожен курс DSA та половина співбесід з програмування вперто говорять про часову складність. Якщо ви можете визначити складність алгоритму, дивлячись на нього, ви можете здогадатися, як він поведе себе на вхідних даних, які ви так і не встигли протестувати. А це, у продакшені, більшість даних.
Чому час виконання є поганим показником алгоритму
То чому б просто не запустити це за допомогою таймера? Багато людей так роблять, і я розумію. Загвоздка в тому, що час виконання тягне за собою купу речей, до яких ваш алгоритм не має жодного стосунку:
- Обладнання. Мій п'ятирічний ноутбук і новенький хмарний сервер дадуть вам разюче різні цифри для одного й того ж скрипта.
- Мова програмування. Напишіть той самий цикл на C та на Python, і ви можете побачити пробіл 10× або більше.
- Завантаження системи. Запускається якийсь фоновий оновлювач, прокидається збирач сміття, кеш холодний. Ваш результат переміщується.
- Які б вхідні дані ви не отримали. Сортування, яке швидко виконується на майже відсортованих даних, може швидко виконуватися на перетасованих даних.
Секундомір видає один пробіг на одному полі з одним вхідним даними. Запитайте його про 100-кратне збільшення даних, і він нічого не дасть.
Кількість кроків не коливається. Той самий алгоритм, ті самі вхідні дані, і ви отримуєте однакову кількість кроків, незалежно від того, чи це Rust на стійковому сервері, чи JavaScript на чиємусь телефоні. Ось чому часова складність — це чесний бій між двома рішеннями, перш ніж ви щось протестуєте. Я б все одно провів би порівняння після цього, якщо це чогось варте. Це просто інше питання.
Пояснення великого O та інших асимптотичних позначень
У підручниках це називається асимптотичною нотацією, що звучить гірше, ніж є насправді. Ви дозволяєте n стати величезним і перестаєте звертати увагу на дрібниці, тому постійні множники та крихітні входи відпадають, і виживає лише крива зростання. Варто знати три з них:
| Нотація | Що це описує | Просте значення | Приклад |
|---|---|---|---|
| Велике O, O(f(n)) | Верхня межа | Алгоритм зростає не швидше, ніж f(n) | Лінійний пошук — це O(n) |
| Велика Омега, Ω(f(n)) | Нижня межа | Алгоритм потребує щонайменше f(n) роботи | Будь-який сорт порівняння є Ω(n log n) |
| Велика Тета, Θ(f(n)) | Щільно пов'язаний | Верхня та нижня межі збігаються | Сортування злиттям – це Θ(n log n) |
На практиці ви почуєте нотацію Big O приблизно у 95% випадків. Вона встановлює верхню межу, тобто час виконання не зростатиме швидше, ніж швидкість у дужках. Під час мого першого огляду коду на реальній роботі старший розробник написав "O(n²), будь ласка, виправте" поруч із вкладеним циклом, і він мав на увазі, що найгірший випадок часової складності буде квадратичним, і список ось-ось стане набагато довшим.
Омега та Тета здебільшого живуть на університетських курсах з аналізу алгоритмів, і я не думаю, що друкував будь-який з них на роботі роками. Великий О перемагає, тому що він відповідає на те, що люди насправді запитують на зустрічі, а саме: "наскільки погано стане, якщо трафік потроїться?"
Є одна технічна деталь, яка мене деякий час бентежила. Оскільки велике O — це лише стеля, функція O(n) також є O(n²), строго кажучи, так само, як людина зростом 1,5 метра є «менше 2,1 метра». Правда, і це марно. Усі наводять найточнішу межу, яку можуть обґрунтувати, і я зроблю те саме.
Загальні класи часової складності з прикладами
У реальному коді ви побачите не так багато класів, можливо, сім, якщо врахувати найстрашніші. Ось приблизно скільки коштує кожен з них при n = 1000:
| Клас | Ім'я | Типовий приклад | Операції при n = 1000 |
|---|---|---|---|
| О(1) | Постійна | Індекс масиву, пошук у хеш-таблиці | 1 |
| O(log n) | Логарифмічний | Бінарний пошук | ~10 |
| O(n) | Лінійний | Сканування списку | 1000 |
| O(n log n) | Лінійно-арифмічний | Сортування злиттям, швидке сортування (усереднення) | ~10 000 |
| O(n²) | Квадратний | Вкладені цикли, бульбашкове сортування | 1 000 000 |
| O(2ⁿ) | Експоненціальний | Наївний рекурсивний Фібоначчі | Більше, ніж атоми у Всесвіті |
| О(н!) | Факториал | Продавець-мандрівник, який використовує грубу силу | Ще більший |
O(1): Постійний час
Незалежно від того, чи має ваш словник Python десять ключів чи десять мільйонів, витяг одного за ключем коштує приблизно однаково, як і читання елементів[5] зі списку. Саме в цій площинності полягає вся суть константного часу.
O(log n): Логарифмічний час
Я вважаю їх алгоритмами типу «вгадай число від 1 до 100», де кожна вгадана величина виключає половину того, що залишилося. Бінарний пошук робить саме це для відсортованого списку:
python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 if arr[mid] == target: return mid if arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1
З мільярдом відсортованих елементів потрібно близько 30 порівнянь, тоді як поетапне переглядання їх по одному може зайняти цілий мільярд, і я ніколи не переставав вважати це кумедним.
O(n) та O(n log n)
Лінійний алгоритм відвідує кожен елемент фіксовану кількість разів, так само, як ви б шукали найбільше число в стовпці електронної таблиці на око. O(n log n) — це дім пристойного сортування. Сортування злиттям розбиває список на окремі елементи (log n рівнів розбиття), а потім виконує один лінійний прохід для кожного рівня під час об'єднання, тому час його виконання залишається незмінним, незалежно від того, чи надходять дані відсортованим чи перемішаним.
O(n²) і гірше
Квадратний код майже завжди має цикл, розміщений всередині іншого циклу, як-от ця перевірка дублікатів, яка порівнює кожну пару:
python def has_duplicate(items): for i in range(len(items)): for j in range(i + 1, len(items)): if items[i] == items[j]: return True return False
Експоненціальне та факторіальне зростання набагато гірші. Підручниковий рекурсивний Фібоначчі постійно розв'язує одні й ті ж підзадачі, тому кожне збільшення на одиницю в n приблизно подвоює роботу. При n = 20 ви цього не помітите; при n = 60 ви можете піти приготувати вечерю, з'їсти її, помити посуд, і вона все одно не буде готова.
Як розрахувати часову складність крок за кроком
Для обчислення часової складності майже ніколи не потрібен формальний доказ. Я прокручую цей список у своїй голові, і він охоплює більшість коду, який я бачу:
- Визначте n. Визначте розмір вхідних даних: довжину списку, кількість вузлів у графі, кількість цифр у числі.
- Порахуйте роботу в кожному рядку. Прості оператори (присвоєння, порівняння, арифметичні дії) коштують O(1).
- Додайте послідовні блоки. Два цикли один за одним, кожен через n, дають n + n = 2n.
- Множення вкладених блоків. Цикл над n всередині іншого циклу над n дає n × n = n².
- Відкиньте константи. 2n стає n, а 500 стає 1.
- Залиште лише домінантний член. У n² + n частина n² переважає решту зі зростанням n.
Швидко розібрався. Виходить T(n) = 3n² + 5n + 2. Вставте мільйон: 3n² — це три трильйони, 5n — це п'ять мільйонів. Помилка округлення. Візьмемо це O(n²), готово.
Цикли, які пропускають один за одним замість того, щоб перестрибувати один, є більш підступними:
python def count_halvings(n): кроки = 0, поки n > 1: n //= 2 кроки += 1 повернути кроки
Кожен прохід скорочує n навпіл, тому цей цикл while завершується приблизно після log₂(n) раундів. Що, по суті, є вся відповідь на питання "коли часова складність становить O(log n)?". Якщо те, що залишилося, зменшується на постійний коефіцієнт на кожному кроці, то все гаразд.
Рекурсії потрібен ще один інструмент – рекурентність. Сортування злиттям виконує дві операції половинного розміру, а потім одне злиття, тому T(n) = 2T(n/2) + n. Головна теорема – це шпаргалка для рекурентностей такої форми, і для цієї вона видає O(n log n).
І емпіричне правило з конкурентного програмування, на яке я дуже спираюся: звичайна машина виконує щось на кшталт 10⁸ простих операцій за секунду. Дуже приблизний результат, але цього достатньо, щоб перевірити часову складність рішення, перш ніж натиснути кнопку «Надіслати». При n, що дорівнює 10⁵, O(n²) становить приблизно 10¹⁰ операцій, тому у вас тайм-аут. O(n log n) менше 2 мільйонів. Пропливає.
Аналіз найгіршого, найкращого та середнього випадків
Якщо ввести один і той самий алгоритм різні вхідні дані, обсяг роботи може різко коливатися. Лінійний пошук чудово це показує:
- У найкращому випадку: ви хочете сидіти попереду. Одне порівняння — і ви вибуваєте.
- У найгіршому випадку: воно в самому кінці або взагалі відсутнє. Це n порівнянь.
- Середній випадок: якщо це може бути будь-де з рівними шансами, ви перевірите в середньому приблизно n/2. Зверніть увагу, що це все ще O(n).
Запитайте розробника про «складність» чогось, і він майже завжди надасть вам найгірший показник часової складності, оскільки це число — обіцянка, навколо якої ви можете планувати.
Скажімо, ваш API обробляє запит у найгіршому випадку за O(n). Чудово, тепер ви знаєте, як поводиться найповільніший запит, і ви також захищені, коли хтось навмисно надсилає вам сміття. Люди точно так роблять: якщо зловмисник визначає, які ключі призводять до зіткнення вашої хеш-таблиці, це єдині ключі, які ви бачитимете деякий час.
Варто розглянути середній випадок, коли поганий сценарій майже не виникає. Швидке сортування є типовим прикладом, усереднюючи його за значенням O(n log n), але скочуючи до O(n²), якщо наївно вибирати опорні точки для вже відсортованих даних. Стандартні бібліотеки обходять це за допомогою випадкових опорних точок або перемикаючись на інший алгоритм сортування, коли рекурсія стає підозріло глибокою.
Що таке складність простору та допоміжний простір?
Пам'ять — це ще один рахунок, який стягує алгоритм. Просторова складність відстежує, скільки її вам потрібно зі збільшенням розміру вхідних даних, і ви записуєте її з тією ж нотацією Big O, що й час.
Частина цієї пам'яті — це сам вхід, за який ви платите незалежно від того, що ви з ним робите. Частина, яку ви фактично контролюєте, називається допоміжним простором, тобто додатковим простором, який ваш код виділяє під час роботи, таким як тимчасові змінні та нові масиви, а також стеком викликів, який ніхто не пам'ятає, доки він його не «вкусить».
Деякі швидкі випадки:
- Для обміну двома змінними потрібна пара слотів незалежно від чогось іншого, тому це допоміжний простір O(1).
- Копіювання списку з n елементів у новий список коштує вам O(n) додаткової пам'яті.
- Рекурсія на n рівнів вглиб залишає n кадрів у стеку, що займає O(n) місця, навіть якщо ви ніколи не створювали масив.
Я спостерігав, як молодший розробник втратив цілий день через цей останній виклик. Здавалося, що його рекурсивна функція взагалі не використовує пам'ять, але кожен незавершений виклик був запаркований на стеку в очікуванні повернення глибших викликів, а при великому вхідному сигналі все зависало через переповнення стеку.
Значна частина оптимізації — це просто обмін пам'яті на час або навпаки. Мемоізація кешує результати, які ви вже обчислили, що зменшує наївний час Фібоначчі з O(2ⁿ) до O(n) в обмін на O(n) пам'яті. Хеш-таблиці купують вам середні пошуки O(1), витрачаючи місце на сегменти. На сервері з 64 ГБ оперативної пам'яті така торгівля зазвичай є очевидною, але на мікроконтролері або всередині смарт-контракту ви б подумали двічі.
Часова та просторова складність поширених структур даних
Вибір правильної структури даних зазвичай кращий за мікроналаштування того, що знаходиться всередині вашого циклу. Середні витрати для тих випадків, до яких ви звертатиметеся найчастіше:
| Структура даних | Доступ | Пошук | Вставка | Видалити | Космос |
|---|---|---|---|---|---|
| Масив | О(1) | O(n) | O(n) | O(n) | O(n) |
| Зв'язаний список | O(n) | O(n) | О(1) | О(1) | O(n) |
| Хеш-таблиця | н/д | О(1) | О(1) | О(1) | O(n) |
| Збалансоване бінарне дерево пошуку | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Бінарна купа | O(1) для мін/макс | O(n) | O(log n) | O(log n) | O(n) |
Дві виноски. Вставка та видалення зв'язаного списку мають значення O(1) лише якщо ви вже маєте вузол. А хеш-таблиця може опуститися до O(n), коли багато ключів зіштовхуються.
Алгоритми сортування різняться так само сильно:
| Алгоритм сортування | Найкращий | Середній | Найгірший | Допоміжний простір |
|---|---|---|---|---|
| Сортування бульбашками | O(n) | O(n²) | O(n²) | О(1) |
| Сортування об'єднанням | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Швидке сортування | O(n log n) | O(n log n) | O(n²) | O(log n) |
| Сортування купою | O(n log n) | O(n log n) | O(n log n) | О(1) |
Сортування злиттям передбачуване, але потребує додаткової пам'яті. Сортування купою сортує на місці та зберігає той самий найгірший випадок. Швидке сортування, незважаючи на менш привабливу стелю, як правило, перемагає на практиці.
Часова складність у блокчейні та смарт-контрактах
Ось тут і починається веселощі. На вашому власному сервері недбалий алгоритм витрачає ресурси процесора та, можливо, дратує користувача. На Ethereum або будь-якому ланцюжку EVM це призводить до марнування грошей. Кожен опкод, який виконує смарт-контракт, коштує пального, що оплачується в рідній монеті ланцюжка, тому кількість ваших операцій відображається у вигляді рядка в чиємусь рахунку. Іншими словами, погана часова складність має свою ціну.
Скажімо, у вас є контракт, який передає винагороду кожному власнику токена. O(n), і витрати на газ зростають з кожним новим власником. У день запуску ніхто цього не помічає.
Потім список власників продовжує зростати. Одного дня для виплати потрібно більше газу, ніж ліміт газу блоку, який є обмеженням на те, скільки газу може поміститися в один блок. Після цього транзакція не може пройти. Не «це повільно». Вона просто ніколи не завершується успішно, і будь-які кошти, що чекали за цією функцією, фактично застрягли. Аудитори реєструють такі необмежені цикли як відмову в обслуговуванні, і це справедливо.
Виправлення полягають у складному мисленні, чистому та простому:
- Розділіть роботу на пакети фіксованого розміру протягом кількох транзакцій.
- Переверніть це так, щоб кожен користувач отримав свою власну винагороду. Кожен виклик є O(1).
- Замініть цикл на доказ Меркла.
Мені подобаються докази Меркла як приклад того, чому log n так важливий у ланцюжку. Дерево Меркла хешує велику купу даних в один кореневий хеш.
Щоб довести, що один запис належить до набору з n, потрібно приблизно log₂(n) хешів. Для мільйона записів це приблизно 20. Не мільйон. Airdrop спираються на це, і легкі біткойн-гаманці використовують той самий трюк для підтвердження транзакції без завантаження всього блоку.
Поза блокчейном, та сама угода. Уявіть собі платіжний бекенд, який зіставляє кожну вхідну транзакцію блокчейну з рахунком-фактурою, скануючи кожну відкриту. O(n) на платіж, і це стає повільнішим у міру зростання магазину. Помістіть рахунки-фактури в хеш-карту, ключ якої задається адресою або ідентифікатором, і кожен збіг буде O(1). А якщо ви не хочете самостійно створювати та обслуговувати цю сантехніку, крипто-платіжний шлюз, такий як Plisio, зробить це за вас.
