O(n) — лінійна складність

Це найпоширеніший тип складності, який ви бачите щодня.

Уявімо, що у вас є масив з 1000 елементів і потрібно знайти одне значення. Якщо масив не відсортований, іншого шляху, окрім як перевірити кожен елемент, просто немає. І саме це означає O(n) — час виконання зростає прямо пропорційно до кількості елементів.

Приклад: лінійний пошук у масиві

function linearSearch($array, $target) {
    for ($i = 0; $i < count($array); $i++) {
        if ($array[$i] === $target) {
            return $i;
        }
    }
    return -1;
}

Класика. Від foreach до array_map або array_filter — більшість ваших ітерацій працює саме в O(n).

O(n) — це ще не погано. Це нормально. Але якщо обробляєте мільйони записів — треба думати, як зробити краще.

← Попередня: O(1) — константна складність · Уся серія · Наступна: O(log n) — логарифмічна складність →

Вперше опубліковано в Telegram-каналі «Створений щоб помирати» 21.06.2025.