Точка входа в программирование

Что Big O говорит о скорости, а что скрывает Два вложенных цикла не обязательно выполняют ровно n² действий. Здесь рассматриваются только пары разных элементов, причём каждая один раз: n = 5 pairs = 0 for i in range(n): for j in range(i + 1, n): pairs += 1 print(pairs) # 10 Число пар — n(n − 1)/2. При росте n главным становится квадрат, поэтому затраты растут как Θ(n²). Удаление половины сравнений улучшает время, но не меняет этот класс роста. Разбор Big O объясняет, что такая оценка не обещает конкретное число миллисекунд. На маленьких данных влияют константы и реализация; для реального времени нужен замер. Всегда уточняйте, что оцениваете: худший случай, средний, время или дополнительную память. Одно O(n) без контекста легко понять неправильно.

Рекурсия: базового случая недостаточно У функции есть условие остановки, но выполнение до него не доходит. Например, вычитать из числа по два и ждать нуля бесполезно, если начали с нечётного числа. Нужно проверить и базовый случай, и движение к нему. В примере сумма цифр вычисляется так: def digit_sum(n): if n < 0: return digit_sum(-n) if n < 10: return n return n % 10 + digit_sum(n // 10) print(digit_sum(1234)) # 10 Для целого неотрицательного числа деление на 10 сокращает задачу, пока не останется одна цифра. Вызовы ждут результатов друг друга и занимают место в стеке. В учебном разборе рекурсии есть задачи на вложенные списки и повторяющиеся подзадачи. Увеличение лимита рекурсии не исправляет алгоритм, который не приближается к остановке.