Здравствуйте!
Добро пожаловать и оставайтесь со мной, пока я объясняю вам Big O Notation самыми простыми словами!
«Общее время, необходимое для выполнения алгоритма» — это самое простое определение Big O Notation, но почему это имеет значение для вас как разработчика?
Чтобы ответить на этот вопрос, ниже приведен простой алгоритм поиска, который находит любой заданный элемент в массиве; если заданного элемента нет в массиве, наш алгоритм возвращает null.
Простой алгоритм поиска.
Fig 1.0 (For-loop search algorithm )
Выше представлен простой цикл For-loop на JavaScript, который перебирает каждый элемент в массиве, проверяет, равна ли текущая итерация нашему входу (‘item’ ), и если элемента нет в массиве, возвращает «null».
Ниже (рис. 2.0) показан цикл while, который делает то же самое, что и вышеприведенный цикл For.
Алгоритм двоичного поиска.
Fig 2.0 (while loop search algorithm )
Хотя приведенные выше функции делают в точности одно и то же. Но что произойдет, если количество элементов в нашем массиве будет расти экспоненциально?
Насколько эффективными будут оба наших алгоритма?
Пошаговое описание алгоритма двоичного поиска:
- Мы сравниваем ‘item’ со средним индексом массива.
- если ‘item’ совпадает со средним индексом, мы возвращаем средний элемент.
- else если ‘item’ больше среднего элемента, длина массива переназначается на средний ( элемент — 1 ).
- else если ‘item’ меньше среднего элемента, начало массива переназначается на середину ( элемент + 1 ).
С помощью этого метода мы удаляем половину массива при первом сравнении.
Для лучшего понимания,
Если длина массива увеличится до 1млн.
С помощью первой функции (рис. 1.0) мы выполним 1 миллион итераций (в худшем случае), чтобы найти наш элемент. Однако со второй функцией мы выполним не более 10 итераций (в худшем случае).
Нотация Big O для наших функций.
Алгоритм простого поиска (рис. 1.0) — O(n) // Плохой парень
Алгоритм двоичного поиска (рис. 2.0) — O(log n) // Хороший парень.
Оставайтесь со мной в этом блоге, пока я объясняю алгоритмы и структуры данных как можно более кратко.
Ставьте ссылки на код и не забывайте давать ему звезду.
https://github.com/Olatisunkanmi/Data-Structures-and-Algorithms-/tree/main/5%20Algorithms/Binary%20Search