Big O Notation: What A-Level CS Actually Expects

Big O notation встречается в каждой основной спецификации A-level по компьютерным наукам (AQA, OCR, Edexcel), и это сбивает с толку множество учащихся — не потому что математика сложная, а потому что они никогда не видят её связи с реальным кодом. Это практическое руководство по тому, что нужно знать и как ответить на экзаменационные вопросы без лишних слов.

Что Big O на самом деле измеряет

Big O описывает, как время выполнения (или объём используемой памяти) алгоритма растёт с увеличением размера входных данных, обычно обозначаемого n. Это не секундомер, который считает секунды. Это способ описать скорость роста, чтобы сравнивать алгоритмы независимо от оборудования.

Когда вы пишете O(n), вы говорите: если я удвою входные данные, объём работы примерно удвоится. O(n²) означает, что удвоение входных данных примерно учетверяет объём работы. Именно эту зависимость экзаменаторы хотят, чтобы вы выявили, а не точные подсчёты операций.

Сложности, которые нужно знать назубок

Для A-level это те, которые появляются снова и снова:

• O(1) – константное время. Обращение к элементу массива по индексу: arr[5]. Размер массива не имеет значения.
• O(log n) – логарифмическое. Бинарный поиск в отсортированном списке. Каждый шаг сокращает пространство поиска вдвое.
• O(n) – линейное. Один проход по списку в цикле, как линейный поиск, проверяющий каждый элемент один раз.
• O(n log n) – линеарифметическое. Merge sort и quicksort (средний случай) находятся здесь.
• O(n²) – квадратичное. Вложенные циклы по одним и тем же данным, что делают bubble sort, insertion sort и selection sort.
• O(2ⁿ) – экспоненциальное. Наивная рекурсивная последовательность Фибоначчи без мемоизации. Быстро становится плохо.

Вы должны уметь посмотреть на псевдокод и назвать нужную сложность с одного взгляда, потому что именно это в основном проверяется.

Чтение кода для определения сложности

Метод, который работает всегда: считайте циклы и посмотрите, как они связаны с n.

# O(n) - один цикл, один проход
for i in range(n):
    print(i)

# O(n^2) - вложенный цикл, оба зависят от n
for i in range(n):
    for j in range(n):
        print(i, j)

# O(log n) - пространство поиска сокращается вдвое на каждой итерации
low, high = 0, n - 1
while low <= high:
    mid = (low + high) // 2
    if target == arr[mid]:
        break
    elif target < arr[mid]:
        high = mid - 1
    else:
        low = mid + 1

Вложенный цикл, диапазон которого зависит от n, остаётся O(n²), даже если выглядит немного иначе (например, for j in range(i) вместо for j in range(n) — это всё ещё квадратично в целом, просто с другим множителем).

Обращайте внимание на циклы, которые вообще не зависят от n. Цикл, который выполняется 10 раз независимо от размера входных данных — это O(1), даже если цикл есть. Экзаменаторы любят так подтасовывать.

Распространённые алгоритмы сортировки и их Big O

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

Алгоритм	Лучший случай	Худший случай
Bubble sort	O(n)	O(n²)
Insertion sort	O(n)	O(n²)
Merge sort	O(n log n)	O(n log n)
Binary search	O(1)	O(log n)
Linear search	O(1)	O(n)

Последовательность merge sort (одна и та же сложность в лучшем и худшем случае) стоит упомянуть явно, если вопрос спрашивает, почему вы выбрали бы его вместо bubble sort для больших наборов данных. Лучший случай bubble sort O(n) работает только с оптимизацией раннего выхода, когда в проходе не происходит обменов — упомяните эту деталь, если вы это упомянули, так как некоторые экзаменационные комиссии это ожидают.

Где ученики теряют баллы

Самое частое: написание