Интервью с PHP: всесторонний анализ распространенных алгоритмов поиска

раннее предупреждение

В этой статье мы познакомим вас с различными алгоритмами поиска и их сложностью. Поскольку мы стремимся быть простыми для понимания, длина может быть больше.Вы можете сначала отметить это и каждый день уделять время, чтобы читать и понимать немного. Эта статья сопровождаетсяGithub Repo, Добро пожаловать на старую железную звезду, она будет постоянно обновляться.

открытие

Подобно сортировке, поиск или поиск также является одним из наиболее часто используемых алгоритмов. Независимо от того, ищем ли мы базу данных или файл, мы на самом деле используем какой-то алгоритм поиска, чтобы найти данные, которые мы ищем.

Линейный поиск

Самый распространенный способ выполнения поиска — сравнение каждого элемента с искомыми данными, это линейный поиск или последовательный поиск. Это самый простой способ поиска. Если в списке n элементов. в худшем случае. Нам нужно обыскать n элементов, чтобы найти конкретный элемент. Следующее перебирает массив, чтобы найти элемент.

function linearSearch(array $arr, int $needle) {
    for ($i = 0, $count = count($arr); $i < $count; $i++) {
        if ($needle === $arr[$i]) {
            return true;
        }
    }

    return false;
}

Сложность линейного поиска

best time complexity	O(1)
worst time complexity	O(n)
Average time complexity	O(n)
Space time complexity	O(1)

бинарный поиск

Средняя или наихудшая временная сложность линейного поиска составляет O (n), которая не меняется при изменении порядка поиска в массиве. Поэтому, если элементы в массиве отсортированы в определенном порядке, нам не нужно выполнять линейный поиск. Мы можем получить лучшие результаты, выполнив выборочный поиск. Наиболее популярным и известным алгоритмом поиска является «двоичный поиск». Хотя немного похоже на то, что мы говорили раньшебинарное дерево поиска, но мы можем использовать этот алгоритм без построения бинарного дерева поиска.

function binarySearch(array $arr, int $needle) {
    $low = 0;
    $high = count($arr) - 1;

    while ($low <= $high) {
        $middle = (int)(($high + $low) / 2);

        if ($arr[$middle] < $needle) {
            $low = $middle + 1;
        } elseif ($arr[$middle] > $needle) {
            $high = $middle - 1;
        } else {
            return true;
        }
    }

    return false;
}

В алгоритме бинарного поиска мы начинаем с середины данных, проверяем, является ли элемент в середине меньше или больше, чем элемент, который мы ищем, и решаем, каким путем идти. Таким образом, мы делим список пополам и полностью отбрасываем половину, как на изображении ниже.

Рекурсивная версия:

function binarySearchRecursion(array $arr, int $needle, int $low, int $high)
{
    if ($high < $low) return false;

    $middle = (int)(($high + $low) / 2);

    if ($arr[$middle] < $needle) {
        return binarySearchRecursion($arr, $needle, $middle + 1, $high);
    } elseif ($arr[$middle] > $needle) {
        return binarySearchRecursion($arr, $needle, $low, $middle - 1);
    } else {
        return true;
    }
}

Анализ сложности бинарного поиска

Для каждой итерации мы делим данные пополам, отбрасываем половину и используем вторую половину для поиска. После 1, 2 и 3 итераций соответственно длина нашего списка постепенно уменьшается до n/2, n/4, n/8... . Следовательно, мы можем обнаружить, что после k итераций останется только n/2^k элементов. Конечным результатом является n/2^k = 1, затем мы логарифмируем обе части, чтобы получить k = log(n), что является наихудшей сложностью времени выполнения алгоритма бинарного поиска.

best time complexity	O(1)
worst time complexity	O(log n)
Average time complexity	O(log n)
Space time complexity	O(1)

Повторить бинарный поиск

Есть такой сценарий, если у нас есть массив с повторяющимися данными, если мы хотим найти первое вхождение 2 из массива, то по предыдущему алгоритму вернет 5-й элемент. Однако, как мы можем ясно видеть на изображении ниже, правильный результат говорит нам о том, что это не 5-й элемент, а 2-й элемент. Следовательно, приведенный выше алгоритм бинарного поиска необходимо изменить, и он преобразуется в повторный поиск, поиск не останавливается до первого появления элемента.

function repetitiveBinarySearch(array $data, int $needle)
{
    $low = 0;
    $high = count($data);
    $firstIndex = -1;

    while ($low <= $high) {
        $middle = ($low + $high) >> 1;

        if ($data[$middle] === $needle) {
            $firstIndex = $middle;
            $high = $middle - 1;
        } elseif ($data[$middle] > $needle) {
            $high = $middle - 1;
        } else {
            $low = $middle + 1;
        }
    }

    return $firstIndex;
}

Сначала мы проверяем, является ли значение, соответствующее середине, тем значением, которое мы ищем. Если это так, то мы присваиваем средний индекс индексу первого вхождения и продолжаем проверять элемент слева от среднего элемента, чтобы увидеть, встречается ли снова искомое значение. Затем продолжайте повторять до тех пор, покавысокий. Если значение снова не найдено, первым вхождением является значение первого индекса элемента. Если нет, верните -1 как обычно. Давайте запустим тест, чтобы увидеть, правильный ли код:

public function testRepetitiveBinarySearch()
{
    $arr = [1,1,1,2,3,4,5,5,5,5,5,6,7,8,9,10];

    $firstIndex = repetitiveBinarySearch($arr, 6);

    $this->assertEquals(11, $firstIndex);
}

Результат оказался правильным.

На данный момент мы можем сделать вывод, что бинарный поиск определенно быстрее, чем линейный поиск. Однако обязательным условием всего этого является то, что массив уже отсортирован. Применение бинарного поиска к несортированному массиву может привести к неправильным результатам. Может возникнуть ситуация, когда для массива мы не уверены, отсортирован ли он. Теперь вопрос в том, должен ли я сначала отсортировать массив, а затем применить алгоритм бинарного поиска? Или продолжать использовать алгоритм линейного поиска?

мелкое мышление

Для массива с n элементами, и они не отсортированы. Поскольку мы знаем, что бинарный поиск быстрее, мы решили сначала отсортировать его, а затем использовать бинарный поиск. Тем не менее, мы знаем, как лучшеАлгоритм сортировки, временная сложность которого в наихудшем случае равна O(nlogn), а для бинарного поиска сложность в наихудшем случае составляет O(logn). Итак, если мы применим бинарный поиск после сортировки, сложность будет O(nlogn).

Однако мы также знаем, что для любого линейного или последовательного поиска (сортированного или несортированного) наихудшая временная сложность составляет O(n), что явно лучше, чем в приведенной выше схеме.

Рассмотрим другой случай, когда нам нужно искать заданный массив несколько раз. Обозначим k как количество раз, которое мы хотим выполнить поиск в массиве. Если k равно 1, то мы можем легко применить предыдущий метод линейного поиска. Если значение k меньше размера массива, пусть n пока представляет размер массива. Если значение k ближе или больше n, то у нас возникают проблемы с применением линейного метода. Предполагая, что k = n, линейный поиск будет иметь сложность O(n2). Теперь, если мы сортируем, а затем ищем, даже если k больше, сортировка займет всего O (nlogn) комплексного времени. Тогда сложность каждого поиска равна O(logn), а сложность n поисков равна O(nlogn). Если мы возьмем здесь наихудший случай, сортировку, а затем поиск k раз, общая сложность составит O(nlogn), что, очевидно, лучше, чем последовательный поиск.

Можно сделать вывод, что если количество операций поиска меньше длины массива, то массив лучше не сортировать, а просто выполнять последовательный поиск. Однако, если количество операций поиска больше по сравнению с размером массива, то лучше сначала отсортировать массив, а затем использовать бинарный поиск.

Существует множество различных версий алгоритма бинарного поиска. Вместо того, чтобы каждый раз выбирать промежуточный индекс, мы можем принять вычислительное решение, чтобы выбрать, какой индекс использовать следующим. Теперь рассмотрим два варианта алгоритма бинарного поиска: интерполяционный поиск и экспоненциальный поиск.

интерполяционный поиск

В алгоритме бинарного поиска процесс поиска всегда начинается с середины массива. Если массив распределен равномерно и искомые данные могут находиться ближе к концу массива, то поиск из середины может оказаться не лучшим вариантом. В этом случае интерполяционный поиск может быть очень полезен. Поиск с интерполяцией — это усовершенствование алгоритма бинарного поиска.Поиск с интерполяцией может выбирать разные позиции в зависимости от значения поиска. Например, если бы мы искали значение в начале массива, оно бы находилось непосредственно в первой части массива, а не в середине. Рассчитайте позицию, используя формулу, как показано ниже.

Видно, что мы перейдем от общего среднего = (низкий * высокий)/2 к более сложному уравнению. Эта формула вернет более высокий индекс, если искомое значение ближе к arr[high], и более низкий индекс, если значение ближе к arr[low].

function interpolationSearch(array $arr, int $needle)
{
    $low = 0;
    $high = count($arr) - 1;

    while ($arr[$low] != $arr[$high] && $needle >= $arr[$low] && $needle <= $arr[$high]) {
        $middle = intval($low + ($needle - $arr[$low]) * ($high - $low) / ($arr[$high] - $arr[$low]));

        if ($arr[$middle] < $needle) {
            $low = $middle + 1;
        } elseif ($arr[$middle] > $needle) {
            $high = $middle - 1;
        } else {
            return $middle;
        }
    }

    if ($needle == $arr[$low]) {
    	return $low;
    } 
    
    return -1;
    
}

Поиск с интерполяцией требует больше вычислительных шагов, но если данные распределены равномерно, средняя сложность этого алгоритма составляет O(log(log n)), что намного лучше, чем сложность O(logn) бинарного поиска. Кроме того, мы должны быть осторожны, если распределение значений неравномерно. В этом случае может потребоваться повторная оценка эффективности интерполяционного поиска. Ниже мы рассмотрим другой вариант бинарного поиска, называемый экспоненциальным поиском.

Поиск по индексу

При бинарном поиске мы ищем заданные данные во всем списке. Экспоненциальный поиск улучшает бинарный поиск, определяя нижнюю и верхнюю границы поиска, чтобы мы не искали весь список. Это уменьшает количество элементов, которые мы сравниваем во время поиска. Экспоненциальный поиск выполняется в следующие два шага:

1. Мы определяем размер границы, находя первый индекс k, где значение 2^k больше, чем искомый термин. Теперь 2^k и 2^(k-1) становятся верхней и нижней границами соответственно. 2. Используйте приведенные выше границы для бинарного поиска.

Давайте посмотрим на код, реализованный на PHP.

function exponentialSearch(array $arr, int $needle): int
{
    $length = count($arr);
    if ($length == 0) return -1;

    $bound = 1;

    while ($bound < $length && $arr[$bound] < $needle) {
        $bound *= 2;
    }

    return binarySearchRecursion($arr, $needle, $bound >> 1, min($bound, $length));
}

Мы помечаем позицию, где $needle появляется как i, тогда временная сложность нашего первого шага равна O(logi). означает, что для нахождения верхней границы наш цикл while должен выполняться O(logi) раз. Поскольку на следующем шаге применяется бинарный поиск, временная сложность также равна O(logi). Мы предполагаем, что j - это количество раз, когда наш последний цикл while выполнялся, тогда диапазон, который нам нужен для поиска этого двоичного поиска, составляет от 2 ^ j-1 до 2 ^ j, и j = logi, то есть

Тогда наша временная сложность бинарного поиска должна быть log2 для этого диапазона, то есть

Тогда временная сложность всего экспоненциального поиска составляет 2 O(logi), без учета константы O(logi).

best time complexity	O(1)
worst time complexity	O(log i)
Average time complexity	O(log i)
Space time complexity	O(1)

хеш-поиск

Хеш-таблицы могут быть очень эффективными структурами данных с точки зрения операций поиска. В хеш-таблице каждый фрагмент данных имеет связанный с ним уникальный индекс. Если мы знаем, на какой индекс смотреть, мы можем очень легко найти соответствующее значение. Обычно в других языках программирования приходится использовать отдельную хеш-функцию для вычисления хэш-индекса хранимого значения. Хэш-функции предназначены для создания одного и того же индекса для одного и того же значения и предотвращения коллизий.

В базовой реализации PHP на C массив сам по себе представляет собой хеш-таблицу.Поскольку массив является динамическим, нет необходимости беспокоиться о переполнении массива. Мы можем хранить значения в ассоциативных массивах, чтобы мы могли связать значения с ключами.

function hashSearch(array $arr, int $needle)
{
    return isset($arr[$needle]) ? true : false;
}

поиск по дереву

Одним из лучших способов поиска иерархических данных является создание дерева поиска. вПонимание и реализация деревьевВ разделе мы увидели, как построить бинарное дерево поиска и повысить эффективность поиска, а также рассмотрели различные способы обхода дерева. Теперь перейдем к двум наиболее часто используемым методам поиска деревьев, обычно называемым поиском в ширину (BFS) и поиском в глубину (DFS).

Поиск в ширину (BFS)

В древовидной структуре корень соединен со своими дочерними узлами, и каждый дочерний узел также может быть представлен в виде дерева. При поиске в ширину мы начинаем с узла (в основном с корневого узла) и сначала посещаем все соседние узлы, прежде чем посещать другие соседние узлы. Другими словами, мы должны двигаться уровень за уровнем при использовании BFS.

Используя BFS, получается следующая последовательность.

Псевдокод выглядит следующим образом:

procedure BFS(Node root)
    Q := empty queue
    Q.enqueue(root)
    
    while(Q != empty) 
        u := Q.dequeue()
        for each node w that is childnode of u
            Q.enqueue(w)
        end for each
    end while
end procedure        

Ниже приведен PHP-код.

class TreeNode
{
    public $data = null;
    public $children = [];

    public function __construct(string $data = null)
    {
        $this->data = $data;
    }

    public function addChildren(TreeNode $treeNode)
    {
        $this->children[] = $treeNode;
    }
}

class Tree
{
    public $root = null;

    public function __construct(TreeNode $treeNode)
    {
        $this->root = $treeNode;
    }

    public function BFS(TreeNode $node): SplQueue
    {
        $queue = new SplQueue();
        $visited = new SplQueue();

        $queue->enqueue($node);

        while (!$queue->isEmpty()) {
            $current = $queue->dequeue();
            $visited->enqueue($current);

            foreach ($current->children as $children) {
                $queue->enqueue($children);
            }
        }

        return $visited;
    }
}

Полные примеры и тесты, которые вы можете нажатьПосмотреть здесь.

Если вы хотите узнать, существует ли узел, вы можете добавить простое условное суждение к текущему значению узла. Наихудшая временная сложность BFS равна O(|V| + |E|), где V — количество вершин или узлов, E — количество соединений между ребрами или узлами, а наихудшая пространственная сложность — O(|V |).

BFS графика похожа на приведенную выше, но немного отличается. Поскольку графы зациклены (могут создаваться циклы), нам нужно убедиться, что мы не посещаем один и тот же узел повторно, чтобы создать бесконечный цикл. Чтобы избежать повторного посещения узлов графа, необходимо отслеживать уже посещенные узлы. Это можно решить с помощью очередей или с помощью алгоритмов раскраски графов.

Поиск в глубину (DFS)

Поиск в глубину (DFS) относится к началу поиска в узле и ответвлениям от целевого узла, чтобы достичь узла как можно глубже. DFS отличается от BFS.Короче говоря, DFS копает глубоко, а не распространяет сначала. Затем DFS возвращается, когда достигает конца ветви, и переходит к следующему доступному соседнему узлу до конца поиска. дерево выше

На этот раз мы получаем другой порядок обхода:

Начните с корня, а затем посетите первого дочернего элемента, который равен 3. Затем перейдите к дочернему узлу 3 и повторите это несколько раз, пока не достигнете нижней части ветки. В DFS мы будем использовать рекурсивный подход для достижения этой цели.

procedure DFS(Node current)
    for each node v that is childnode of current
       DFS(v)
    end for each
end procedure

 public function DFS(TreeNode $node): SplQueue
{
    $this->visited->enqueue($node);

    if ($node->children) {
        foreach ($node->children as $child) {
            $this->DFS($child);
        }
    }

    return $this->visited;
}

Если вам нужно использовать итеративную реализацию, вы должны помнить об использовании стека вместо очереди, чтобы отслеживать следующий посещаемый узел. В следующей реализации используется итеративный метод

public function DFS(TreeNode $node): SplQueue
{
    $stack = new SplStack();
    $visited = new SplQueue();

    $stack->push($node);

    while (!$stack->isEmpty()) {
        $current = $stack->pop();
        $visited->enqueue($current);

        foreach ($current->children as $child) {
            $stack->push($child);
        }
    }

    return $visited;
}

Это очень похоже на алгоритм BFS. Основное отличие состоит в том, что для хранения посещенных узлов вместо очереди используется стек. Это повлияет на результат. Приведенный выше код выведет 8 10 14 13 3 6 7 4 1. Это отличается от вывода алгоритма, который мы использовали итеративно, но в этом результате нет ничего плохого.

Поскольку стек используется для хранения дочерних элементов определенного узла. Для корневого узла со значением 8 сначала помещается первый дочерний узел со значением 3, затем в стек помещается 10. Поскольку число 10 помещается позже, оно следует LIFO. Итак, если мы реализуем DFS с использованием стека, вывод всегда начинается с последней ветви на первую ветвь. В код DFS можно внести несколько небольших изменений для достижения желаемого эффекта.

public function DFS(TreeNode $node): SplQueue
{
    $stack = new SplStack();
    $visited = new SplQueue();

    $stack->push($node);

    while (!$stack->isEmpty()) {
        $current = $stack->pop();
        $visited->enqueue($current);

        $current->children = array_reverse($current->children);
        foreach ($current->children as $child) {
            $stack->push($child);
        }
    }

    return $visited;
}

Поскольку стек следует принципу «последний пришел, первый вышел» (LIFO), путем реверсирования вы можете гарантировать, что первый узел будет посещен первым, поскольку порядок обратный, стек фактически работает как очередь. Если бы мы искали бинарное дерево, нам не понадобилась бы какая-либо инверсия, потому что мы могли бы сначала выбрать правый дочерний элемент, а затем сначала извлечь левый дочерний элемент.

Временная сложность DFS аналогична сложности BFS.