• Оценка сложности

Оценка сложности алгоритмов: линейная сложность, квадратичная, логарифмическая...

Существует несколько способов измерения сложности алгоритма. Программисты обычно сосредотачивают внимание на скорости алгоритма, но не менее важны и другие показатели – требования к объёму памяти, например. Использование быстрого алгоритма не приведёт к ожидаемым результатам, если для его работы понадобится больше памяти, чем есть у компьютера.

При сравнении различных алгоритмов важно знать, как их сложность зависит от объёма входных данных.

$T(n): N -> Q^+ (>0)$

$T(n)=O(f(n))$ <=> сущ. C,N_0>0: T(n) \leq C*f(n), \all n \geq n_0

Лемма

$T(n) = a_0 * x^b + a_1 * x^{b-1} + ... + a_{n-1}*x^{1} + a_n*x^{0}$ $T(n) \leq c*x^b$ $n_0 = 1$ $c = |a_0| + |a_1| + ... $

Лемма 2

$\all k \geq 1, n^k \neq O(n^{k-1})$ \let (пусть) n^k = O(n^{k-1}) => \exist )C, $n^k \leq C * n^{k-1}$ $n \leq C, \forall n \geq n_0$

Худший случай..

$T(n) = \omega (f(n)) <=> \exist c,n_0 > 0: T(n) \geq c*f(n), \forall n \geq n.

$T(n) = \theta(f(n))$ \Leftrightarrow $T(n) = O(f(n))$ и $T(n) = \omega(f(n))$

$\exists c_1, c_2, n_0: C_1*f(n) \leq T(n) \leq C_2 * f(n), \forall n > n_0$

$\forall k > 0$ ...

Маленькая $o$

$T(n) = o(f(n))$ <=> $\forall c>0 \exists n_0:$ $T(n) \leq C*f(n)$ $\forall n \geq n_0$

Пример: $\forall k \geq 1$, $n^{k-1} = o(n^k)$

$O(1)$ - время выполнения алгоритма константа (не зависит от количества элементов во входном множестве).

$O(n)$ - линейная сложность.

Пример: поиск минимального элемента в массиве (цикл по всем элементам массива).

$O(n^2)$ - квадратичная сложность. Например, сортировки "пузырьком", вставками и т.д.

Пример: поиск двух точек на плоскости с максимальным расстоянием между ними.

$O(n^3)$ - кубическая сложность.

Пример: поиск треугольника максимальной площади с вершинами в точках на плоскости (перебор вершин тройным циклом).

Оценка $O(n)$ ассимптотическая (при $n$ стремящемся к бесконечности).

$O(\ln{n})$ - Бинарный поиск - логарифмическая сложность.

$O(n\log{n})$ - быстрая сортировка Хоара (рус) - QuickSort, HeapSort, MergeSort.

При оценке сложности важна только самая старшая степень. Например:

$O(n^3+n^2+4n)=O(n^3)$

Константа так же отбрасывается, так как нам важно лишь во сколько раз возрастает время выполнения программы при увеличении размера входных данных.