Оценка временной сложности алгоритма

определение временной сложности
Временная сложность алгоритма— это функция (зависит от размера входных данных) равная максимальному количеству элементарных операций, проделываемых алгоритмом для решения экземпляра задачи указанного размера.

Временная сложность подразделяется:
- В худшем случае
- В среднем
- В наилучшем

Временная сложность описывается большой буквой "О". Такие сокращения называются О-нотацией. В О-нотации не учитываются константы и коэффициенты. Константы не могут принципиально изменить применимость алгоритма на практике.
Виды зависимостей
  • O ( n ) — линейная зависимость;
  • O ( log n ) — логарифмическая зависимость.
  • O( n^2 ) — квадратичная зависимость.
  • O( n^3 ) — кубическая зависимость.
  • O( 2^n ) —экспоненциальная зависимость .
  • O( 1 ) — константная зависимость. алгоритма не зависит от размера входных данных, и выполняется константное количество операций.

«n» — это количество элементов, находящихся в данный момент в контейнере.
Операции CPython
На первом этапе необходимо понимать оценку временной сложности различных базовых операций CPython. Из простых операций строятся все алгоритмы и необходимо учитывать временную сложность каждой операции.
Список list
Внутри список представлен как динамический массив; самые большие затраты связаны с выходом за пределы текущего размера выделения:

вставкой элементов
удалением.

Если вам нужно добавить/удалить элементы на концах массива, рассмотрите использование collections.deque.

Статья про динамический массив
Двухсторонняя очередь Deque
Deque имеет внутренне представление двух связанного списка. Добавление, удаление, получение элементов в концы очереди эффективно, а в середину медленно
Множество set
Оценка временной сложности для множества схожа со словарем
Словарь Dict
Оценка временной сложности для множества схожа со словарем
Временная оценка конструкций языка
Оценка временной сложности также зависит ок конструкция языка, которые вы используете в алгоритме.

O(1) - если программа не содержит цикла, рекурсии и вызова любой другой функции с непостоянным временем. Цикл или рекурсия, которая выполняется постоянное количество раз, также считается O (1).
for i in range(10):
     print(i)
Временная оценка конструкций языка
O(n) - если переменные цикла увеличиваются/уменьшаются на постоянную величину. Например, следующие функции имеют временную сложность O(n).
s=[1,2,3,4,5]
for i in range(len(s)):
     print(i)
Составные классы сложности
При сложении двух классов сложности складываются функции этих классов.

O( f(n) ) + O( g(n) ) = O ( f(n) + g(n) )


* меньший член выражения отбрасывается

Пример:
O( n ) + O( log n ) = O ( n + log n ) = O(n)