Узнайте, как рассчитать сложные алгоритмы в рекордно короткие сроки!
Это вторая глава, посвященная вычислениям с асимптотическими обозначениями. В этой статье мы узнаем, как рассчитать временную и пространственную сложность алгоритма. Если вы хотите освежить свои знания об асимптотическом анализе: что такое асимптотические обозначения, для чего нужны асимптотические обозначения — просто прочитайте предыдущую статью.
Правила BigO
Как разработчика, нас больше всего интересует наихудший случай временной или пространственной сложности нашего алгоритма, поэтому мы возьмем обозначение BigO. Для вычисления нотации BigO нам нужно знать некоторые из основных правил асимптотической нотации:
Правило сумм: если f1(n) ∈ O(g(n)) и f2(n) ∈ O (g(n)), то f1(n) + f2(n) ∈ O(g(n)).
Доказательство:если f1(n) ∈ O(g(n)) и f2(n) ∈ O (g(n)) должны существовать константы c1, n1, c2, n2такие, что f1( n) ≤ c * 1g(n) ∀ n ≥ n1 и f2(n) ≤ c2 * g(n) ∀ n ≥ n2. Таким образом, если мы выберем c3 = c1 + c2и n3 = max(n1, n2), мы имеем, что если n ≥ n3, тогда f(n) + g(n) ≤ c * 1g(n) + c2 * g(n) = (c1 + c2) * g(n) = c3 * g(n). Таким образом, f1(n) + f2(n) равно O(g(n)).
Правило постоянного фактора: если f1(n)∈ O(g(n)) тогда k * f1(n) ∈ O(g(n)) для любой константы k
Пример: n³ + 10 * n² + log(n) ∈ O(n³), поскольку 10 * n² ∈ O(n²) ⊂ O( n³)и log(n) ∈ O(log(n)) ⊂ O(n³). По правилу сумм n³ + 10 * n² + log(n) ∈ O(n³)
Правило произведения: если d(n) ∈ O(f(n)) и e(n) ∈ O(g(n)), то d(n) * e(n) ∈ O(f(n) * g( п))
Пример: (1 + 10 * n) * (2 * log(n) + 3) ∈ O(n * log(n)). По правилу постоянного множителя (1 + 10 * n) ∈ O(n) и (2 * log(n) + 3) ∈ O(log(n))
n^x ∈ O(a^n) для любых фиксированных x › 0 и a › 1. Однако a^n !∈ O(n^x) для любых фиксированных x › 0 и a › 1
Пример: n¹⁰⁰⁰∈ O(1,0001^n). Однако константы c и n0, для которых n¹⁰⁰⁰ ≤ c * (1,0001^n) ∀ n ≥ n0очень велики.
log(n^x) ∈ O(log(n)) для любого фиксированного x › 0
Доказательство: log(n^x) = x * log(n)∈ O(log(n)) (по правилу постоянного множителя)
loga(n) ∈ O(logb(n)) для любых фиксированных a › 1, b › 1
Доказательство: loga(n) = logb(n) / logb(a) ∈ O(logb(n))(по правилу постоянного множителя)
Расчеты BigO
Чтобы вычислить сложность алгоритма, нам нужно посчитать BigO для каждого оператора этого алгоритма. Итак, нам необходимо:
- Разбейте нашу функцию на отдельный оператор
- Рассчитать BigO для каждого утверждения
- Суммируйте все BigO
- Использование правил приводит к более простой форме и сортирует ее по скорости роста
- Определить термин высшего порядка
Для пятого пункта можно использовать Таблицу важных наборов BigO от меньшего к большему. Найти его можно в предыдущей части или воспользовавшись шпаргалкой BigO.
Давайте посмотрим на один пример:
Мы разбили функцию на операторы. Теперь посчитаем BigO для каждого оператора — посчитаем количество вычислительных шагов.
Как мы видим, первый не зависит от размера входных данных, поэтому можно сказать, что он занимает постоянное количество вычислительных шагов — сложность 1 равна O(1).
Второй оператор — это цикл for. Мы не знаем: сколько раз выполняется тело for, нам нужно подсчитать это, глядя на то, что делает код. Как видим, третье утверждение не зависит от размера входных данных, поэтому требует постоянного количества вычислительных шагов — O(1), но выполнил N раз, поэтому сложность будет O(N*C), где C — это константа, поэтому мы можем записать ее как O(N).
Последний оператор также требует постоянного количества вычислительных шагов — это будет O(1).
Теперь нам нужно суммировать все BigO:
O(1 + N + 1) = O(2 + N) = O(2) + O(N) = O(1) + O(N)
И последний шаг — определить наивысший порядковый номер, в нашем случае — O(N). Теперь мы можем сказать, что функция суммы имеет значение BigO равное N — O(N).
Как определить некоторые из BigO?
O(1) — оператор, который не зависит от размера входных данных — имеет постоянное количество вычислительных шагов
O(N) — количество операций увеличивается линейно с размером входных данных — для циклов:
O(N²) — производительность прямо пропорциональна квадрату размера входных данных — вложенные циклы:
O(log(n)) — переменные цикла делятся/умножаются на постоянную величину (как в бинарном поиске):
Шпаргалка
Хорошо использовать шпаргалку, где вы можете найти сложность общих операций со структурами данных, алгоритмы сортировки массивов и диаграмму сложности BigO. Шпаргалку BigO можно погуглить, а для ленивых можно найти здесь.
