Что такое сложность алгоритма — пример ответа на собеседовании PHP Разработчик

Что такое сложность алгоритма

«Что такое сложность алгоритма» — вопрос из категории Алгоритмы и структуры данных, который задают на 28% собеседований PHP Разработчик. Ниже — развёрнутый ответ с разбором ключевых моментов.

Тип вопроса: Алгоритмы и структуры данных Вероятность: 28% Категория: PHP Разработчик

Ответ

Сложность алгоритма — это оценка количества ресурсов (времени или памяти), которые потребуются алгоритму для выполнения в зависимости от размера входных данных.

Основные виды сложности:

O(1) — константная (например, доступ к элементу массива по индексу).
O(n) — линейная (например, поиск в неотсортированном массиве).
O(log n) — логарифмическая (например, бинарный поиск).
O(n²) — квадратичная (например, пузырьковая сортировка).

Пример:

// O(n) — линейная сложность  
function linearSearch(array $arr, int $target): bool {  
    foreach ($arr as $value) {  
        if ($value === $target) return true;  
    }  
    return false;  
}

Чем меньше сложность, тем эффективнее алгоритм на больших данных.