Всем привет! Каждый программист часто сталкивается с выполнением рутинных задач, которые уже были решены до него, и не просто решены, а решены эффективно. Эта публикация открывает цикл статей посвященных самым известным алгоритмам в программировании.
В ней мы поговорим о том - что такое алгоритмы, зачем они нужны и разберем наш первый алгоритм - бинарный поиск.
Меня зовут Антон. Я занимаюсь front-end разработкой и сейчас я расскажу вам об алгоритмах в программировании.
Что такое алгоритм?
Сейчас я постараюсь дать максимально короткое и понятное определение алгоритма.
Алгоритм - набор инструкций для выполнения некоторой задачи.
Получается, любой фрагмент кода можно назвать алгоритмом? Да, верно, но некоторые алгоритмы справляются с одной задачей лучше, чем другие. Именно о таких алгоритмах мы и будем говорить.
Но как мы поймем какой алгоритм работает лучше, а какой хуже? Все очень просто! Для описания скорости работы алгоритма мы будет использовать специально введенное обозначение O ( О-большое).
"О-большое" описывает, насколько быстро работает алгоритм
Допустим, что у нас имеется список из 100 элементов. Простой поиск элемента в этом списке должен проверить каждый элемент, сравнить каждый элемент с искомым. В таком случае время выполнения "O-большое" будет O(100).
А если одна операция занимает 1 миллисекунду, то такой поиск в худшем случае составит 100 миллисекунд.
Типичны примеры "O-большого"
Как мы видим из примера выше, O-большое не показывает время выполнения алгоритма, а показывает количество операций. То есть, чем меньше операций, тем более эффективный алгоритм.
Бинарный поиск
Каждый из нас хоть раз сталкивался с такой задачей, когда нужно было найти определенный элемент в отсортированном массиве. И как мы уже разобрали выше, скорость поиска элемента в массиве равна O(n). То есть, если у нас 100 элементов, а одна операция занимает 1 миллисекунду, то в худшем случае нам потребуется 100 миллисекунд, чтобы найти нужны элемент.
Звучит неплохо, даже довольно быстро покажется на первый взгляд, но есть одно НО. А если мы представим, что у нас нет 100 элементов в массиве, а 100 000. То там, в лучшем случае, нам потребуется 100 000 миллисекунд или же 1.5 минуты. А это просто непозволительное время для поиска элемента в приложении
Что же делать в таком случае? На помощь нам приходит бинарный поиск.
Для того, чтобы понять как работает бинарный поиск давай сыграем в одну игру. Я задаю число от 1 до 100, а вы попробуете его отгадать. При каждой попытке я буду говорить больше или меньше названное число искомому.
Если вы начнете просто перебирать числа от 1 до 100, то потратите очень много попыток на поиск этого числа, но можно поступить иначе...
Если вы начнете с середины, с 50, к примеру, то сможете сразу отсечь половину элементов в массиве. Допустим, что 50 слишком мало, то теперь вы рассматриваете числа в промежутке от 51 до 100.
Вы опять называете середу промежутка - это число 75. И если число 75 слишком много, то теперь искомый промежуток всего от 51 до 74. Диапазон поиска заметно сократился. И далее, по такому принципу, вы будет называть числа пока какое-то не будет искомым.
Для большей наглядности работы бинарного поиска давайте сравним два алгоритма:
Да, бинарный поиск работает в разы быстрее и именно поэтому в задачах, где вам необходимо найти элемент в отсортированном массиве, он ваш главный помощник
Ниже я приведу пример реализации этого алгоритма на языке JavaScript
Заключение
В этой статье мы поговорили о том, что такое алгоритмы, разобрались что такое "O-большое" и написали алгоритм бинарного поиска. Обращаю ваше внимание на то, что бинарный поиск работает только в том случае, если массив элементов отсортирован, в противном случае он работать не будет. А про алгоритмы сортировки мы поговорим в следующих статьях.
Если статья была полезна, то подпишись и поставь свой лайк, удачи)
#it #web #proweb #frontend #code #top #алгоритмы #код #программирование