Easy📖Теория7 min

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

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

AlgoBasics

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

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

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

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

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

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

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

PHPGo
// 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)

// Summing slice elements
func sumArray(arr []int) int {
    total := 0                  // 1 operation
    for _, x := range arr {     // n iterations
        total += x              // 1 operation per iteration
    }
    return total                // 1 operation
}
// Total: 1 + n*1 + 1 = n + 2 -> O(n)
### Цикл с шагом 2 — всё равно O(n)
PHPGo
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)

func everyOther(arr []int) {
    for i := 0; i < len(arr); i += 2 { // n/2 iterations
        fmt.Println(arr[i])
    }
}
// n/2 -> O(n) (constant 1/2 is dropped)
### Цикл до половины — O(n)
PHPGo
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)

func firstHalf(arr []int) {
    half := len(arr) / 2
    for i := 0; i < half; i++ { // n/2 iterations
        fmt.Println(arr[i])
    }
}
// n/2 -> O(n)
## Анализ вложенных циклов

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

PHPGo
// 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²)

// All pairs of elements
func allPairs(arr []int) {
    n := len(arr)
    for i := 0; i < n; i++ {         // n iterations
        for j := 0; j < n; j++ {     // n iterations inside
            fmt.Printf("%d %d\n", arr[i], arr[j])
        }
    }
}
// n * n = n² -> O(n²)
### Вложенный цикл с убыванием — O(n²)
PHPGo
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²)

func upperTriangle(arr []int) {
    n := len(arr)
    for i := 0; i < n; i++ {
        for j := i; j < n; j++ {   // (n-i) iterations
            fmt.Printf("%d %d\n", arr[i], arr[j])
        }
    }
}
// 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³)

PHPGo
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³)

func triplets(arr []int) {
    n := len(arr)
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            for k := 0; k < n; k++ {
                fmt.Printf("%d %d %d\n", arr[i], arr[j], arr[k])
            }
        }
    }
}
// n * n * n = n³ -> O(n³)
## Последовательные блоки

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

PHPGo
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

func mixedOperations(arr []int) {
    n := len(arr)

    // Block 1: O(n)
    for _, x := range arr {
        fmt.Println(x)
    }

    // Block 2: O(n²)
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            fmt.Printf("%d %d\n", i, j)
        }
    }

    // Block 3: O(n)
    for _, x := range arr {
        fmt.Println(x * 2)
    }
}
// O(n) + O(n²) + O(n) = O(n²)
// Take the highest degree
## Анализ циклов с делением — O(log n)

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

PHPGo
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)

func halvingLoop(n int) int {
    count := 0
    for n > 1 {
        n = 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)
### Удвоение переменной цикла
PHPGo
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)

func doublingLoop(n int) int {
    i := 1
    count := 0
    for i < n {
        i *= 2
        count++
    }
    return count
}
// n=16: i = 1,2,4,8,16  (4 steps)
// -> O(log n)
### Цикл внутри логарифмического — O(n log n)
PHPGo
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)

func nLogNExample(arr []int) {
    n := len(arr)
    step := 1
    for step < n {                    // log n iterations
        for i := 0; i < n; i++ {     // n iterations inside
            fmt.Printf("%d %d\n", step, i)
        }
        step *= 2
    }
}
// log(n) * n = O(n log n)
## Анализ рекурсии

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

PHPGo
// 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)

// Factorial: n -> (n-1) -> (n-2) -> ... -> 1
func factorial(n int) 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)
PHPGo
// Naive Fibonacci
function fib(int $n): int
{
    if ($n <= 1) {
        return $n;
    }
    return fib($n - 1) + fib($n - 2);
}

// Naive Fibonacci
func fib(n int) 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)

PHPGo
// 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)

// Recursive binary search
func binarySearchRec(arr []int, target, left, right int) int {
    if left > right {
        return -1
    }
    mid := (left + right) / 2
    if arr[mid] == target {
        return mid
    } else if 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)
PHPGo
// 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)

// Merge Sort: split in half + linear merge
func mergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    mid := len(arr) / 2
    left := mergeSort(arr[:mid])    // T(n/2)
    right := mergeSort(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

PHPGo
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;
}

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

Задача 2

PHPGo
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;
        }
    }
}

func mystery2(arr []int) {
    n := len(arr)
    for i := 0; i < n; i++ {
        j := 1
        for j < n {
            fmt.Printf("%d %d\n", arr[i], j)
            j *= 2
        }
    }
}
Ответ: Внешний — O(n), внутренний — O(log n). Итого: **O(n log n)**.

Задача 3

PHPGo
function mystery3(int $n): int
{
    if ($n <= 1) {
        return 1;
    }
    return mystery3(intdiv($n, 2)) + mystery3(intdiv($n, 2));
}

func mystery3(n int) int {
    if n <= 1 {
        return 1
    }
    return mystery3(n/2) + mystery3(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. Знай сложность встроенных операций своего языка

Проверь себя

🧪

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

🧪

Какова временная сложность рекурсии? ```php function mystery(int $n): int { if ($n <= 1) return 1; return mystery(intdiv($n, 2)) + mystery(intdiv($n, 2)); } ```

🧪

Какой тип рекурсии в этом коде и какова его сложность? ```php function factorial(int $n): int { if ($n <= 1) return 1; return $n * factorial($n - 1); } ```

🧪

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

🧪

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

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

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

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

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

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