Один проход по данным
O(n) означает линейное время: объём работы растёт вместе с размером входных данных. Вдвое больше элементов — вдвое больше шагов.
В PHP линейное время обычно выглядит как один цикл foreach по массиву. Любой алгоритм, который обязан хотя бы взглянуть на каждый элемент — суммирование, подсчёт, поиск в неотсортированном массиве — не может быть быстрее O(n).
Линейная сложность — это хорошая сложность. Миллионы элементов не проблема для одного прохода.
Линейный поиск
Если массив не отсортирован, единственный способ найти значение — проверять элементы один за другим, с начала. Это линейный поиск.
В худшем случае — значение последнее или его вообще нет — цикл посещает все n элементов. Именно этот худший случай и описывает O(n).
Найти значение и его позицию
Цикл проверяет "one", "two", "three", прежде чем доходит до "four" — 4 шага для совпадения по индексу 3. break останавливает цикл сразу же, как значение найдено.
Вывод: PHP-скрипт
<?php
$words = ["one", "two", "three", "four", "five"];
$steps = 0;
foreach ($words as $i => $w) {
$steps++;
if ($w === "four") {
echo "найдено по индексу $i, шагов: $steps\n";
break;
}
}
Посещение каждого элемента
Многие повседневные задачи — это один проход по всему массиву: сложить все значения, хранить наибольшее из встреченных, подсчитать элементы, проходящие проверку. Каждый элемент затрагивается ровно один раз, поэтому все они O(n).
Два или три таких прохода подряд — по-прежнему линейная сложность: O(2n) и O(3n) сводятся к O(n).
Сложить все элементы
Цикл добавляет каждый элемент к $sum. 8 элементов, 8 сложений — классическая форма одного прохода.
Вывод: PHP-скрипт
<?php
$nums = [3, 1, 4, 1, 5, 9, 2, 6];
$sum = 0;
foreach ($nums as $n) {
$sum += $n;
}
echo "сумма ", count($nums), " элементов: $sum\n";
Найти наибольшее значение
$max начинается с первого элемента; каждый элемент, который больше, заменяет его. После одного прохода остаётся наибольшее значение, 9.
Вывод: PHP-скрипт
<?php
$nums = [3, 1, 4, 1, 5, 9, 2, 6];
$max = $nums[0];
foreach ($nums as $n) {
if ($n > $max) {
$max = $n;
}
}
echo "наибольшее значение: $max\n";
Подсчитать совпадения
Цикл проверяет каждое слово условием strlen($w) > 3 и считает попадания. Три слова длиннее 3 букв.
Вывод: PHP-скрипт
<?php
$words = ["one", "two", "three", "four", "five"];
$count = 0;
foreach ($words as $w) {
if (strlen($w) > 3) {
$count++;
}
}
echo "слов длиннее 3 букв: $count\n";