Знать сложность чужого алгоритма недостаточно: на собеседовании и в работе нужно быстро оценить собственный код. Для этого есть простой порядок действий и список «скрытых» дорогих операций, которые чаще всего всё портят.

Пять конструкций Python, которые выглядят как O(1), но скрывают линейную работу или n log n
Пять конструкций Python, которые выглядят как O(1), но скрывают линейную работу или n log n

Пошаговая оценка

  1. Определите размеры входа: n, m, k. Не всё равно n.
  2. Пройдите по коду сверху вниз и подпишите стоимость каждой строки или блока.
  3. Последовательные блоки складываются, вложенные умножаются.
  4. В цикле умножайте стоимость тела на число итераций (если тело дороже на поздних итерациях, считайте сумму).
  5. Оставьте доминирующее слагаемое и отбросьте константы.
  6. Отдельно посчитайте память: что растёт вместе со входом (копии, словари, стек рекурсии).
python
def count_pairs(a, target):         # n = len(a)
    a = sorted(a)                   # O(n log n)
    lo, hi = 0, len(a) - 1          # O(1)
    cnt = 0
    while lo < hi:                  # at most n iterations
        s = a[lo] + a[hi]           # O(1) per iteration
        if s == target:
            cnt += 1
            lo += 1
            hi -= 1
        elif s < target:
            lo += 1
        else:
            hi -= 1
    return cnt                      # total: O(n log n) + O(n) = O(n log n)

print(count_pairs([1, 2, 3, 4, 5, 6], 7))
print(count_pairs([5, 1, 5, 2, 8], 10))
text
3
2

Сортировка стоит O(n log n), цикл с двумя указателями O(n): по правилу суммы остаётся O(n log n).

Скрытые стоимости