Примеры Big O на PHP

O(1) - Константное время

// Время выполнения не зависит от размера входных данных
function getFirstElement(array $arr) {
    return $arr[0] ?? null; // Всегда одна операция
}

// Пример использования
$array = [1, 2, 3, 4, 5];
echo getFirstElement($array); // O(1)

O(n) - Линейное время

// Время растет линейно с размером данных
function findElement(array $arr, $value) {
    foreach ($arr as $item) { // n операций
        if ($item === $value) {
            return true;
        }
    }
    return false;
}

// Пример
$numbers = range(1, 1000);
findElement($numbers, 500); // O(n) - в худшем случае 1000 проверок

O(n²) - Квадратичное время

// Двойной вложенный цикл (пузырьковая)
function bubbleSort(array $arr) {
    $n = count($arr);
    for ($i = 0; $i < $n; $i++) { // n раз
        for ($j = 0; $j < $n - 1; $j++) { // n раз
            if ($arr[$j] > $arr[$j + 1]) {
                // swap
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
            }
        }
    }
    return $arr;
}

// Пример
$data = [5, 3, 8, 1, 2];
bubbleSort($data); // O(n²) = 25 операций при n=5

O(log n) - Логарифмическое время

// Бинарный поиск, массив должен быть отсортирован!
function binarySearch(array $arr, $target) {
    $low = 0;
    $high = count($arr) - 1;
    
    while ($low <= $high) { // Уменьшаем область поиска вдвое каждый раз
        $mid = floor(($low + $high) / 2);
        
        if ($arr[$mid] === $target) {
            return $mid;
        }
        
        if ($arr[$mid] < $target) {
            $low = $mid + 1;
        } else {
            $high = $mid - 1;
        }
    }
    
    return -1;
}

// Пример
$sortedArray = range(1, 1000000);
binarySearch($sortedArray, 733999); // O(log n) ~ 20 операций

O(n log n) - Линейно-логарифмическое время

// Быстрая сортировка (quicksort)
function quickSort(array $arr) {
    if (count($arr) < 2) {
        return $arr;
    }
    
    $pivot = $arr[0];
    $left = $right = [];
    
    for ($i = 1; $i < count($arr); $i++) {
        if ($arr[$i] < $pivot) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }
    
    return array_merge(
        quickSort($left),
        [$pivot],
        quickSort($right)
    );
}

// Пример
$unsorted = [10, 5, 3, 8, 7, 2, 4];
quickSort($unsorted); // O(n log n)

O(2ⁿ) - Экспоненциальное время

// Числа Фибоначчи (рекурсивная реализация)
function fibonacci(int $n) {
    if ($n <= 1) {
        return $n;
    }
    
    return fibonacci($n - 1) + fibonacci($n - 2); // Два рекурсивных вызова
}

// Пример (очень медленно для больших n)
echo fibonacci(10); // O(2ⁿ) - 1024 операций при n=10

O(n!) - Факториальное время

// Генерация всех перестановок
function permutations(array $items) {
    if (count($items) <= 1) {
        return [$items];
    }
    
    $result = [];
    foreach ($items as $key => $value) {
        $copy = $items;
        unset($copy[$key]);
        
        foreach (permutations($copy) as $permutation) {
            $result[] = array_merge([$value], $permutation);
        }
    }
    
    return $result;
}

// Пример (очень быстро растет)
$perms = permutations(['A', 'B', 'C']); // O(n!) = 6 перестановок
// Для 10 элементов будет 3,628,800 перестановок, для 20! ≈ 2.4×10¹⁸ (это больше, чем звезд в нашей галактике)

назад