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