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

Как оценивать сложность алгоритма

Сначала определить n, затем посчитать, сколько раз выполняется доминирующая операция.

Шпаргалка

array[i]                         // O(1)
list.get(i) // ArrayList         // O(1)
list.get(i) // LinkedList        // O(n)
map.get(key) // HashMap average  // O(1), не абсолютная гарантия
treeMap.get(key)                 // O(log n)
Arrays.sort(int[])               // O(n log n) worst для актуальной JDK-реализации

Циклы

for (int i = 0; i < n; i++) work();        // Θ(n)
for (int i = 1; i < n; i *= 2) work();     // Θ(log n)
for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) work();    // Θ(nm)

Не считать только строки кода. list.contains(x) внутри цикла по n элементам делает решение O(n²), хотя визуально это один вызов.

Рекурсия

Записать recurrence:

• binary search: T(n) = T(n/2) + O(1) = O(log n);
• merge sort: T(n) = 2T(n/2) + O(n) = O(n log n);
• наивный Fibonacci: две перекрывающиеся ветви → экспоненциальный рост.

Практический порядок проверки

1. Время worst case.
2. Дополнительная память.
3. Глубина рекурсии и риск stack overflow.
4. Стоимость подготовки: сортировка ради одного binary search может быть дороже linear scan.
5. Число обращений к сети/БД — часто важнее локальной Big O.

См. Big O, Оценка асимптотической сложности алгоритмов.

На собеседовании

• Два последовательных цикла по n? O(n + n) = O(n).
• Вложенные циклы n и m? O(nm).
• Почему вызов метода нельзя считать O(1)? Нужно раскрыть его реализацию.
• Когда сортировать ради поиска невыгодно? При одном запросе: O(n log n) подготовки против O(n) scan.