Big O Notation: What A-Level CS Actually Expects

Big O нотація з'являється в кожній основній специфікації 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) застосовується тільки з оптимізацією раннього виходу, коли жодних обмінів не відбувається на проходженні — згадайте цю деталь, якщо ви про це говорите, тому що деякі екзаменаційні комісії це очікують.

Де студенти втрачають бали

Найголовніше: писання