🤔 Как посчитать функцию если внутри неё много различных действий?

Сложность функции можно оценить с помощью Big O (O-нотация) – это способ понять, как увеличивается время работы функции при росте входных данных.

🚩Определение сложности по Big O

Константные операции (+, -, *, /, if, return) считаются за O(1).
Циклы (for, while) увеличивают сложность** (например, for на N итераций → O(N)).
Вложенные циклы (for внутри for) дают O(N²).
Рекурсия учитывается как глубина рекурсии.

🚩Примеры расчёта сложности

Простая функция (O(1)) – не зависит от входных данных

function addNumbers($a, $b) {
    return $a + $b;
}

Линейная сложность O(N) (цикл)

function printNumbers($n) {
    for ($i = 0; $i < $n; $i++) {
        echo $i;
    }
}

Квадратичная сложность O(N²) (вложенные циклы)

function printPairs($n) {
    for ($i = 0; $i < $n; $i++) {
        for ($j = 0; $j < $n; $j++) {
            echo "($i, $j) ";
        }
    }
}

Логарифмическая сложность O(log N) (деление пополам, бинарный поиск)

function binarySearch($arr, $target) {
    $left = 0;
    $right = count($arr) - 1;

    while ($left <= $right) {
        $mid = floor(($left + $right) / 2);
        
        if ($arr[$mid] == $target) {
            return $mid;
        } elseif ($arr[$mid] < $target) {
            $left = $mid + 1;
        } else {
            $right = $mid - 1;
        }
    }
    return -1;
}

Факториальная сложность O(N!) (перебор всех вариантов)

function factorial($n) {
    if ($n == 1) return 1;
    return $n * factorial($n - 1);
}

🚩Как считать сложность функции с разными действиями?

Если в функции разные действия, считаем их отдельно и берём наибольшую сложность.

function complexFunction($n) {
    // O(1)
    $sum = 0;

    // O(N)
    for ($i = 0; $i < $n; $i++) {
        $sum += $i;
    }

    // O(N²)
    for ($i = 0; $i < $n; $i++) {
        for ($j = 0; $j < $n; $j++) {
            echo "Hello";
        }
    }

    return $sum;
}

Ставь 👍 и забирай 📚 Базу знаний