Большое-О простыми словами: почему один код быстрее другого

O(n), O(n²), O(log n) — за этими значками прячется одна простая идея: как растёт время работы, когда данных становится больше. Объясняем без формул.

Редакция CodeChick·22 мая 2026 г.·9 мин чтения

«Большое-О» звучит как высшая математика, но идея за ним — бытовая: насколько хуже станет, если данных будет в десять раз больше.

Главный вопрос

Big O не отвечает «сколько секунд работает код». Он отвечает на другое: как растёт время, когда растёт размер входа. Это важнее, потому что данные имеют свойство расти.

O(n) — линейно

Прошли по списку один раз: вдвое больше элементов — вдвое больше работы.

def find_max(nums):
    best = nums[0]
    for n in nums:        # n шагов
        if n > best:
            best = n
    return best

O(n²) — квадратично

Цикл внутри цикла. Вдвое больше данных — вчетверо больше работы. На больших объёмах — боль.

def has_duplicate(nums):
    for i in range(len(nums)):       # n
        for j in range(i + 1, len(nums)):  # ещё n
            if nums[i] == nums[j]:
                return True
    return False

O(log n) — логарифмически

Каждый шаг выбрасывает половину данных, как в поиске слова в словаре. Миллион элементов — около двадцати шагов. Это очень быстро.

Зачем это вам

На собеседовании и в реальном коде вопрос «а что будет на миллионе записей?» решает Big O. Научитесь видеть вложенные циклы — и половина оптимизаций станет очевидной.

#computer science#алгоритмы#сложность