График роста
| Класс | Название | Операций при n = 1 | Где встречается |
|---|
Что такое O-нотация
Зачем она нужна. Один и тот же алгоритм на разных компьютерах работает с разной скоростью, поэтому измерять его в секундах бессмысленно. O-нотация отвечает на другой вопрос: как быстро растет число операций, когда растет размер входа n (это и есть асимптотическая сложность). Это свойство самого алгоритма, а не железа.
Константы не важны. Алгоритмы за 2n и за 100n операций относятся к одному классу O(n): при больших n оба растут линейно. O-нотация сознательно огрубляет оценку, чтобы видеть главное - форму кривой роста.
Как читать график. По горизонтали - размер входа n, по вертикали - число операций. Кривые O(2ⁿ) и O(n!) почти сразу упираются в потолок графика: их значения при n = 30 не помещаются ни на одном экране. Именно поэтому переборные алгоритмы перестают работать уже на крошечных входах, а сортировка за O(n log n) спокойно справляется с миллиардами элементов.
Практическое правило. Смотрите в таблицу значений: при n = 30 разница между O(n) и O(n!) - это разница между тридцатью операциями и числом с 33 цифрами. Выбор алгоритма важнее выбора компьютера.
Не только время. O-нотация описывает рост любого ресурса. Чаще всего ею меряют время - число операций, как на графике ниже. Но точно так же записывают и сложность по памяти: сколько дополнительной памяти нужно алгоритму сверх входных данных. Например, сортировке пузырьком хватает O(1) памяти, а сортировка подсчетом тратит O(n + k) - покупает линейное время дополнительной памятью. У каждого алгоритма две оценки: по времени и по памяти, и часто одну можно выменять на другую.