Что такое временная сложность алгоритмов и как она измеряется

Что проверяют

Умеете ли вы предсказать поведение программы на больших данных по самому коду, а не по ощущениям. В Python это заметно раньше, чем в компилируемом языке: интерпретатор дорог, константа велика, и неудачно выбранная структура данных выстреливает быстро.

Как отвечать

Временная сложность это зависимость числа элементарных операций от размера входа, записанная асимптотически: O отбрасывает константы и младшие слагаемые, оставляя характер роста. O(1) константа, O(log n) двоичный поиск, O(n) проход, O(n log n) сортировка, O(n²) вложенный цикл.

Стоит проговорить, что случаев три: худший, средний и амортизированный. list.append амортизированно константен, потому что ёмкость растёт кратно, а dict и set дают на поиск средний O(1), а не гарантированный.

Дальше самое ценное это сложность встроенных операций, потому что чаще решает именно она:

• проверка x in lst линейна, та же проверка по множеству константна;
• lst.insert(0, x) и lst.pop(0) линейны, у collections.deque оба конца константны;
• срез копирует, поэтому цикл со срезами тихо становится квадратичным;
• sorted это Timsort, O(n log n) и близко к линейному на частично упорядоченных данных.

Закончить стоит измерением: timeit на нескольких размерах входа плюс профиль показывают константу, которую формула прячет.

Где спотыкаются

Называют сложность временем работы. Формула не знает ни про интерпретатор, ни про кэш процессора: на маленьком входе список обгоняет множество, и это не противоречит асимптотике, а лишь напоминает, что она про рост.

Считают только явные циклы. Строка вида проверки вхождения в список или конкатенация строк в цикле выглядят как одна операция, а дают лишний множитель n, и алгоритм из линейного становится квадратичным без единого вложенного for.

Думают, что библиотека меняет сложность. Векторизация и расширение на C уменьшают константу, иногда в десятки раз, но квадратичный алгоритм остаётся квадратичным. Асимптотику меняет только другой алгоритм или другая структура данных, например словарь вместо линейного поиска.