Перейти к основному содержимому

26. Базовые алгоритмы

Понимание базовых алгоритмов критически важно для написания эффективного кода и решения сложных задач в PHP-разработке.

Как вы перевернете строку в PHP?​

Junior

Ответ: Перевернуть строку можно несколькими способами в зависимости от кодировки (ASCII vs UTF-8). Подробный гайд

  • Junior: Используйте strrev().
  • Middle: Используйте ручной цикл for (побайтово).
  • Senior: Используйте подход, безопасный для многобайтовых строк (например, mb_str_split()).
// Junior
function reverseString(string $str): string {
    return strrev($str);
}

// Senior (безопасно для UTF-8)
function mb_strrev(string $string, string $encoding = null): string {
    $chars = mb_str_split($string, 1, $encoding ?: mb_internal_encoding());
    return implode('', array_reverse($chars));
}

Что такое линейный поиск и как он реализуется в PHP?​

Junior

Ответ: Линейный поиск — простейший алгоритм поиска. Он последовательно проверяет каждый элемент списка, пока не найдёт целевое значение или не дойдёт до конца списка.

  • Сложность: O(n).
  • Применение: Небольшие наборы данных или неотсортированные списки.
function linearSearch(array $arr, $target): int
{
    foreach ($arr as $index => $value) {
        if ($value === $target) {
            return $index;
        }
    }
    return -1;
}

Что такое бинарный поиск и какие у него требования?​

Junior

Ответ: Бинарный поиск — быстрый алгоритм поиска, который работает путём многократного деления интервала поиска пополам.

  • Требование: Массив должен быть отсортирован.
  • Сложность: O(log n).
function binarySearch(array $arr, $target): int
{
    $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;
}

Что такое сортировка пузырьком (Bubble Sort)?​

Junior

Ответ: Сортировка пузырьком — простой алгоритм сортировки, который многократно проходит по списку, сравнивает соседние элементы и меняет их местами, если они расположены в неправильном порядке. Этот процесс повторяется, пока список не будет отсортирован.

  • Сложность: O(n²).
  • Применение: В учебных целях или для очень маленьких наборов данных.
function bubbleSort(array $arr): array
{
    $n = count($arr);
    for ($i = 0; $i < $n; $i++) {
        for ($j = 0; $j < $n - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                // Обмен элементов
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
            }
        }
    }
    return $arr;
}

Как работает быстрая сортировка (Quick Sort)?​

Middle

Ответ: Быстрая сортировка — алгоритм «разделяй и властвуй». Он выбирает элемент в качестве «опорного» (pivot) и разделяет массив вокруг него так, чтобы элементы меньше опорного были слева, а большие — справа. Затем рекурсивно сортирует подмассивы.

  • Сложность: O(n log n) в среднем, O(n²) в худшем случае.
function quickSort(array $arr): array
{
    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));
}

Что такое сортировка слиянием (Merge Sort) и в чём её главное преимущество?​

Middle

Ответ: Сортировка слиянием — ещё один алгоритм «разделяй и властвуй». Он делит массив на две половины, рекурсивно сортирует их, а затем объединяет отсортированные половины.

  • Преимущество: Гарантированная сложность O(n log n) даже в худшем случае. Кроме того, это «устойчивая» (stable) сортировка.
function mergeSort(array $arr): array
{
    $count = count($arr);
    if ($count <= 1) {
        return $arr;
    }

    $mid = (int)($count / 2);
    $left = array_slice($arr, 0, $mid);
    $right = array_slice($arr, $mid);

    return merge(mergeSort($left), mergeSort($right));
}

function merge(array $left, array $right): array
{
    $result = [];
    while (count($left) > 0 && count($right) > 0) {
        if ($left[0] <= $right[0]) {
            $result[] = array_shift($left);
        } else {
            $result[] = array_shift($right);
        }
    }
    return array_merge($result, $left, $right);
}

Где следует применять эти алгоритмы в реальной PHP-разработке?​

Middle

Ответ:

  1. Оптимизация поиска: Используйте бинарный поиск, когда имеете дело с большим статичным отсортированным набором данных (например, поиск по большому отсортированному списку ID или наименований товаров).
  2. Управление ресурсами: Очереди (FIFO) применяются для обработки фоновых задач (например, Laravel Queues, RabbitMQ) — для таких задач, как отправка писем, без блокировки основного запроса.
  3. Парсинг: Стеки (LIFO) или рекурсивные алгоритмы используются для разбора структурированных данных (HTML, XML или пользовательские шаблонизаторы) для проверки корректности вложенности тегов и скобок.
  4. Представление данных: Алгоритмы сортировки необходимы для отображения данных в определённом порядке (по алфавиту, по цене, по дате).