Бинарный поиск и "О-большое"

К сожалению, в последнее время встречаю всё больше людей, которые совсем не знакомы с темой алгоритмов. Аргументируют это тем, что "да зачем мне это нужно, если я пилю крадики" и они правы. Разница только в том, что с таким подходом далеко не уедешь и велика вероятность так и пилить крадики до конца своей карьеры. Лично я считаю, что действительно не стоит сразу слишком глубоко копать в эту тему, но базовые принципы знать обязательно. Как минимум базовые понятия встречаются во многих книгах, статьях и видео. И чтобы правильно понять, что до вас хочет донести автор — нужно чуть-чуть разобраться.

Представьте, что ваш друг загадал число, от 1 до 100, а вам нужно его отгадать. При каждой попытке друг будет давать вам один из трёх ответов "Мало" , "Много", "В точку!". Если перебирать все варианты подряд (1, 2, 3, 4... то есть прямым поиском), то вы рискуете использовать 100 попыток, при самом плохом случае.

👌 Но что если вы сразу ударите в середину и назовете число 50? "Мало", и вы сразу отсекли половину вариантов. Затем "75" — "Много", и еще половина вариантов ушла. Именно так и работает бинарный поиск.

❗️Важно, что бинарный поиск работает только в том случае, если список отсортирован.

📌 Время выполнения и "О-большое"

💁‍♂️ Возможно вы забыли что такое логарифм, но точно помните, что такое возведение в степень. Так вот, запись log(2) 8 означает, в какую степень нужно возвести 2, чтобы получить 8, итак log(2) 8 = 3.

"О-большое" описывает, насколько быстро работает алгоритм. Простой поиск должен проверить каждый элемент. Для списка из 4 миллиардов (или любое другое n) чисел потребуется до 4 миллиар­дов попыток. Таким образом, максимальное количество попыток совпадает с размером списка. Такое время выполнения называется линейным и обозначается O(n).

С бинарным поиском дело обстоит иначе. Для списка из 4 миллиардов элементов, потребуется не более более 32 попыток. Впечатляет, да? Бинарный поиск выполняется за логарифмическое время и его сложность описывается как O(log n).

❓ Если это время, то где же секунды?

А их здесь нет. "О-большое" не сообщает время в секундах, а позволяет сравнить количе­ство операций. Оно указывает, насколько быстро возрастает время выполнения алгоритма. А время в секундах уже будет зависеть от размера исходных данных, вычислительных мощностей и т.д.

❗️ "О-большое" определяет время выполнения в худшем случае.

То есть если ваш друг, загадал число "1", то при прямом поиске вы угадаете его моментально, так как оно стоит на первом месте O(1). Но простой поиск всё равно выполняется за время O(n), фактически это утверждение о том, что в худшем случае придется перебрать все числа.

👍 Надеюсь стало немного понятнее и теперь, когда в разных книгах или статьях вы встретите записи типа O(n), O(n!), O(n log n) вы не будете впадать в ступор, а будете осознанно понимать, что автор хочет до вас донести.

#junior #algorithm #source

Хеш-таблицы, HashTables (part-1)

Ну что, отпуск окончен, теперь с новыми силами пришла пора приступить к статьям :) Здесь речь пойдёт именно о структуре данных. То есть пока мы не будем вдаваться во внутренности php (например под капотом языка массивы реализованы именно с помощью хеш-таблиц).

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

Пока звучит сложно, но сейчас попробуем разобраться ;) Для начала определимся с тем, что такое хеширование.

👉 Хеширование — операция, которая преобразует любые входные данные в строку (реже число) фиксированной длины. Функция, реализующая алгоритм преобразования, называется "хеш-функцией", а результат называют "хешем" или "хеш-суммой". Наиболее известны CRC32, MD5 и SHA (много разновидностей). Также стоит упомянуть, что хеш не имеет возможности быть преобразованным обратно в исходные данные.

Для решения нашей задачи хеш-функция принимает в качестве аргумента какой-то элемент (который нужно вставить в хеш-таблицу), а в результате выдает позицию заданного элемента в хеш-таблицы (то есть индекс). Любая операция внутри хеш-таблицы начинается с того, что ключ каким-либо образом преобразуется в индекс обычного массива.

❗️ Например, на картинке выше мы видим, что хеш-функция сопоставила ключ John Smith с индексом 873, а далее в хеш-таблицу под этим индексом было записано значение, а если быть точным, то комплексный объект, содержащий исходный ключ и значение (в нашем случае номер телефона).

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

$key = 'John Doe';
$index = crc32($key) % 1000; // по модулю
print_r($index); // => 434

📌 В данном примере мы используем так называемое "адресное пространство", которое задаёт размеры нашей хеш-таблицы. Так как мы получаем остаток от деления на 1000, то все значения нашего индекса будут лежать в диапазоне от 0 до 999. Возникает вопрос "может ли случиться так, что для разных ключей будет рассчитан один и тот же индекс?" — может, но это не значит, что значения затрутся. Структура таблицы станет чуть сложнее, незначительно вырастет вычислительная сложность, но подробнее об этом в следующем посте ;)

❗️ Главное, что ваша хеш-функция должна:

1. Быстро вычислять хеш (индекс), в разных источниках можно встретить понятие "адрес", это одно и то же;
2. Всегда возвращать один и тот же адрес для одного и того же ключа;
3. Использует все адресное пространство с одинаковой вероятностью;

❓ Зачем так всё усложнять?

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

#middle #algorithm #source