EasyТеория13 min

Временная сложность

Как считать временную сложность алгоритмов: циклы, рекурсия, вложенные конструкции

AlgoBasics

Что такое временная сложность?

Временная сложность — это количество элементарных операций, которые выполняет алгоритм в зависимости от размера входных данных n. Мы не измеряем время в секундах, а считаем шаги.

Элементарные операции:

  • Сравнение двух чисел
  • Арифметическая операция (+, -, *, /)
  • Присваивание переменной
  • Доступ к элементу массива по индексу
  • Возврат значения из функции

Анализ простых циклов

Один цикл — O(n)

// Summing array elements
function sumArray(array $arr): int
{
    $total = 0;              // 1 operation
    foreach ($arr as $x) {   // n iterations
        $total += $x;        // 1 operation per iteration
    }
    return $total;           // 1 operation
}
// Total: 1 + n*1 + 1 = n + 2 -> O(n)
### Цикл с шагом 2 — всё равно O(n) 
function everyOther(array $arr): void
{
    for ($i = 0; $i < count($arr); $i += 2) { // n/2 iterations
        echo $arr[$i] . "\n";
    }
}
// n/2 -> O(n) (constant 1/2 is dropped)
### Цикл до половины — O(n) 
function firstHalf(array $arr): void
{
    $half = intdiv(count($arr), 2);
    for ($i = 0; $i < $half; $i++) { // n/2 iterations
        echo $arr[$i] . "\n";
    }
}
// n/2 -> O(n)
## Анализ вложенных циклов

Два вложенных цикла — O(n²)

// All pairs of elements
function allPairs(array $arr): void
{
    $n = count($arr);
    for ($i = 0; $i < $n; $i++) {         // n iterations
        for ($j = 0; $j < $n; $j++) {     // n iterations inside
            echo $arr[$i] . ' ' . $arr[$j] . "\n";
        }
    }
}
// n * n = n² -> O(n²)
### Вложенный цикл с убыванием — O(n²) 
function upperTriangle(array $arr): void
{
    $n = count($arr);
    for ($i = 0; $i < $n; $i++) {
        for ($j = $i; $j < $n; $j++) {   // (n-i) iterations
            echo $arr[$i] . ' ' . $arr[$j] . "\n";
        }
    }
}
// Sum: n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 -> O(n²)
Визуализация количества итераций: 
i=0: j проходит [0, 1, 2, 3, 4]  -> 5 итераций
i=1: j проходит [1, 2, 3, 4]     -> 4 итерации
i=2: j проходит [2, 3, 4]        -> 3 итерации
i=3: j проходит [3, 4]           -> 2 итерации
i=4: j проходит [4]              -> 1 итерация
                                     --------
                              Итого: 15 = 5*6/2 = n(n+1)/2

Три вложенных цикла — O(n³)

function triplets(array $arr): void
{
    $n = count($arr);
    for ($i = 0; $i < $n; $i++) {
        for ($j = 0; $j < $n; $j++) {
            for ($k = 0; $k < $n; $k++) {
                echo $arr[$i] . ' ' . $arr[$j] . ' ' . $arr[$k] . "\n";
            }
        }
    }
}
// n * n * n = n³ -> O(n³)
## Последовательные блоки

Когда блоки идут друг за другом, складываем сложности.

function mixedOperations(array $arr): void
{
    $n = count($arr);

    // Block 1: O(n)
    foreach ($arr as $x) {
        echo $x . "\n";
    }

    // Block 2: O(n²)
    for ($i = 0; $i < $n; $i++) {
        for ($j = 0; $j < $n; $j++) {
            echo "$i $j\n";
        }
    }

    // Block 3: O(n)
    foreach ($arr as $x) {
        echo ($x * 2) . "\n";
    }
}
// O(n) + O(n²) + O(n) = O(n²)
// Take the highest degree
## Анализ циклов с делением — O(log n)

Деление переменной цикла пополам

function halvingLoop(int $n): int
{
    $count = 0;
    while ($n > 1) {
        $n = intdiv($n, 2);
        $count++;
    }
    return $count;
}
// n=16: 16->8->4->2->1  (4 steps = log2(16))
// n=1024: 10 steps = log2(1024)
// -> O(log n)
### Удвоение переменной цикла 
function doublingLoop(int $n): int
{
    $i = 1;
    $count = 0;
    while ($i < $n) {
        $i *= 2;
        $count++;
    }
    return $count;
}
// n=16: i = 1,2,4,8,16  (4 steps)
// -> O(log n)
### Цикл внутри логарифмического — O(n log n) 
function nLogNExample(array $arr): void
{
    $n = count($arr);
    $step = 1;
    while ($step < $n) {             // log n iterations
        for ($i = 0; $i < $n; $i++) { // n iterations inside
            echo "$step $i\n";
        }
        $step *= 2;
    }
}
// log(n) * n = O(n log n)
## Анализ рекурсии

Линейная рекурсия — O(n)

// Factorial: n -> (n-1) -> (n-2) -> ... -> 1
function factorial(int $n): int
{
    if ($n <= 1) {
        return 1;
    }
    return $n * factorial($n - 1);
}
// Recursion depth: n
// Work at each level: O(1)
// Total: O(n)
### Двоичная рекурсия — O(2^n) 
// Naive Fibonacci
function fib(int $n): int
{
    if ($n <= 1) {
        return $n;
    }
    return fib($n - 1) + fib($n - 2);
}
Дерево рекурсии для `fib(5)`: 
                    fib(5)
                   /      \
              fib(4)      fib(3)
             /    \        /    \
         fib(3)  fib(2)  fib(2)  fib(1)
         /   \    / \     / \
     fib(2) fib(1) ...  ...
      / \
  fib(1) fib(0)

Каждый уровень удваивает количество вызовов: 1, 2, 4, 8, ... = O(2^n).

Рекурсия с делением пополам — O(log n)

// Recursive binary search
function binarySearchRec(array $arr, int $target, int $left, int $right): int
{
    if ($left > $right) {
        return -1;
    }
    $mid = intdiv($left + $right, 2);
    if ($arr[$mid] === $target) {
        return $mid;
    } elseif ($arr[$mid] < $target) {
        return binarySearchRec($arr, $target, $mid + 1, $right);
    } else {
        return binarySearchRec($arr, $target, $left, $mid - 1);
    }
}
// Single branch recursion, halving -> O(log n)
### Рекурсия с делением и линейной работой — O(n log n) 
// Merge Sort: split in half + linear merge
function mergeSort(array $arr): array
{
    if (count($arr) <= 1) {
        return $arr;
    }
    $mid = intdiv(count($arr), 2);
    $left = mergeSort(array_slice($arr, 0, $mid));   // T(n/2)
    $right = mergeSort(array_slice($arr, $mid));      // T(n/2)
    return merge($left, $right);                      // O(n) work for merging
}
// T(n) = 2*T(n/2) + O(n) = O(n log n)
## Мастер-теорема (упрощённо)

Для рекурсий вида T(n) = a * T(n/b) + O(n^d):

Условие Результат Пример
d > log_b(a) O(n^d) —
d = log_b(a) O(n^d log n) Merge Sort: a=2,b=2,d=1
d < log_b(a) O(n^log_b(a)) —

Merge Sort: a=2, b=2, d=1. log_2(2) = 1 = d. Значит O(n log n).

Сложность встроенных операций

PHP

Операция array (indexed) array (assoc)
Доступ по индексу/ключу O(1) O(1)*
Поиск (in_array) O(n) —
isset / array_key_exists — O(1)*
Вставка (append []) O(1)* O(1)*
array_unshift O(n) O(n)
unset по ключу O(1)* O(1)*
sort / usort O(n log n) —
array_merge O(n) O(n)

* — амортизированно

Типичные паттерны и их сложности

Один цикл по n элементов                    -> O(n)
Два вложенных цикла по n                    -> O(n²)
Цикл с делением пополам                     -> O(log n)
Цикл внутри деления пополам                 -> O(n log n)
Рекурсия с двумя ветвями, глубина n         -> O(2^n)
Рекурсия с двумя ветвями, деление пополам   -> O(n log n)
Перебор всех подмножеств                    -> O(2^n)
Перебор всех перестановок                   -> O(n!)

Практика: определи сложность

Задача 1

function mystery1(int $n): int
{
    $count = 0;
    $i = $n;
    while ($i > 0) {
        for ($j = 0; $j < $n; $j++) {
            $count++;
        }
        $i = intdiv($i, 2);
    }
    return $count;
}
Ответ: Внешний цикл — O(log n), внутренний — O(n). Итого: **O(n log n)**.

Задача 2

function mystery2(array $arr): void
{
    $n = count($arr);
    for ($i = 0; $i < $n; $i++) {
        $j = 1;
        while ($j < $n) {
            echo $arr[$i] . ' ' . $j . "\n";
            $j *= 2;
        }
    }
}
Ответ: Внешний — O(n), внутренний — O(log n). Итого: **O(n log n)**.

Задача 3

function mystery3(int $n): int
{
    if ($n <= 1) {
        return 1;
    }
    return mystery3(intdiv($n, 2)) + mystery3(intdiv($n, 2));
}
Ответ: Два рекурсивных вызова, каждый с n/2. T(n) = 2T(n/2) + O(1). По мастер-теореме: a=2, b=2, d=0 → log_2(2) = 1 > 0 → **O(n)**.

Запомни: Чтобы определить временную сложность: 1) Посчитай количество итераций каждого цикла, 2) Умножь вложенные, сложи последовательные, 3) Для рекурсии — нарисуй дерево вызовов или используй мастер-теорему. 4) Отбрось константы и младшие члены.

Итоги

  1. Простой цикл по всем элементам = O(n)
  2. Вложенные циклы = произведение итераций
  3. Деление пополам в любой форме = log n
  4. Рекурсия: считай количество вызовов и работу в каждом
  5. Последовательные блоки = берём максимальную сложность
  6. Знай сложность встроенных операций своего языка

Проверь себя

5 из 8

Какова сложность операции `list.Insert(0, item)` для `List<T>` в C#?

Какова сложность операции `array_unshift($arr, $value)` в PHP?

Какова общая сложность этого кода? ```php function process(array $arr): void { $n = count($arr); for ($i = 0; $i < $n; $i++) { for ($j = $i; $j < $n; $j++) { echo $arr[$j]; } } } ```

Какова сложность операции `arr.insert(0, x)` для списка в Python?

Какова временная сложность? ```php function mystery(int $n): int { $count = 0; for ($i = 0; $i < $n; $i++) { $j = 1; while ($j < $n) { $count++; $j *= 2; } } return $count; } ```

Связанные темы

Пространственная сложность

Связанная тема

Очередь

Связанная тема

Веб-разработка и паттерны

Связанная тема