Временная и пространственная эффективность алгоритма(готовая версия) - 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.

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

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

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

Основные классы эффективности

image