Временная и пространственная эффективность алгоритма - EcsFlash/DataTypes GitHub Wiki

Cуществует два вида эффективности - временная и пространственная. Время выполнения большинства алгоритмов напрямую зависит от размеров вводимых данных. Поэтому эффективность алгоритмов описывают в виде функций от некоторого параметра N связанного с размером входных данных.

Временная эффективность

Единицами измерения эффективности являются основные операции или количество основных операций. Основная операция - операция которая вносит наибольший вклад во время выполнения алгоритма. Таким образом, эффективность алгоритма оценивается по количеству основных операций которые должен выполнить алгоритм при обработке входных данных размера N.

Основные правила оценки:

* Константные операции (присваивание, арифметика) - O(1).
* Циклы — сложность зависит от количества итераций. - O(n)
* Вложенные циклы — сложность умножается. - O(n^2), O(n^3) 
* Рекурсия — сложность зависит от глубины вызовов. - O(n log n)

С асимптотическими оценками важно помнить: они показывают СКОРОСТЬ ЗАМЕДЛЕНИЯ программы в зависимости от количества входных данных. Еще прикол состоит в том что если в коде есть что-то подобное:

for i:=0; i < n; i++ {
     //do smth
}
for j:=0; j < n; j++ {
    //do smth
}

то это не O(2n), а O(n).

Приближенные значения порядка роста(от лучшего к худшему):

n -> log2N -> NlogN -> N^2 -> N^3 -> 2^n -> N!

Также разделяют эффективность в худшем, лучшем и среднем случаях. Эти эффективности рассматриваются в том случае когда есть зависимость не только от размера входных данных но и от других параметров. Например поиск какого либо элемента обычным проходом в неупорядоченном массиве может выполниться как за константное время(если искомый элемент окажется первым) - лучший случай O(1), так и за линейное время(искомый элемент стоит последним) - одновременно средний и худший случай O(n).

Пространственная сложность

Пространственная сложность — это объем дополнительной памяти, который использует алгоритм в зависимости от размера входных данных n.

Основные правила оценки:

• Входные данные обычно не учитываются (если алгоритм их не копирует)( обля, вот и указатели пригодились ).
• Рекурсия учитывает стек вызовов.
• Дополнительные структуры данных (массивы, хеш-таблицы) учитываются.

Честно, я хз как они собрались учитывать хеш-таблицы при подсчете дополнительно задействованной памяти, но допустим - я помечу их курсивом. Наверное это всё что можно рассказать об оценках алгоритмов. В дальнейшем я буду приводить таблицы оценок для каждого алгоритма.