В Части 1 я попытался объяснить две простейшие сложности — сложности с постоянным и квадратичным временем. Я не учел две другие временные сложности наиболее распространенных алгоритмов: O(log(n)) и O(nlog(n)).
В этой части мы поговорим о сложности O(log(n)) и об одном из наиболее часто встречающихся приложений — Двоичный поиск. . Если вы хотите узнать, как алгоритм бинарного поиска выглядит в реальной жизни, скорее всего, вы его уже видели. Одной из наиболее распространенных реализаций бинарного поиска является быстрое автозаполнение на вашем телефоне.
Я наткнулся на очень простое для понимания, но элегантное объяснение log(n) в ответе на stackoverflow от Джона Ферминеллы -
Наиболее распространенные атрибуты логарифмической функции времени выполнения:
выбор следующего элемента, над которым нужно выполнить какое-либо действие, является одной из нескольких возможностей, и
нужно будет выбрать только один.
or
элементы, над которыми выполняется действие, являются цифрами n
Вот почему, например, поиск людей в телефонной книге занимает O(log n). Вам не нужно проверять каждого человека в телефонной книге, чтобы найти нужного; вместо этого вы можете просто разделять и властвовать, глядя на то, где находится имя в алфавитном порядке, и в каждом разделе вам нужно только изучить подмножество каждого раздела, прежде чем вы в конечном итоге найдете чей-то номер телефона….
Визуально это выглядит так-
Давайте представим, что у нас есть массив n. Обычно, когда мы ищем, наши программы инициализируют весь ввод. Это грязно, быстро и экономит много времени при разработке, когда наш размер ввода невелик. Что, если наш массив n содержит несколько миллионов целых чисел? А если еще больше? Как мы можем искать в этом, не исчерпав памяти.
Легко: мы разделяем и властвуем.
- Мы берем половину элементов и делаем массив.
- Если средний элемент не является тем элементом, который мы ищем, мы берем половину нового массива и сравниваем средний элемент теперь меньшего массива. Мы продолжаем этот процесс до тех пор, пока элемент не будет найден или у нас не останется массив только из одного элемента.
- Если элемент не найден в этом процессе разделения и завоевания, то мы повторяем этот процесс на другой половине исходного массива.
Для простоты сначала давайте итеративно закодируем это на Ruby-
def binary_search(original_array, element_im_looking_for) max_index = original_array.length - 1 min_index = 0 while(max_index >= min_index) midpoint = (max_index + min_index)/2 if original_array[midpoint] > element_im_looking_for max_index = midpoint - 1 elsif original_array[midpoint] < element_im_looking_for min_index = midpoint + 1 elsif original_array[midpoint] == element_im_looking_for return midpoint end end return nil end
Этот алгоритм работает очень быстро, потому что мы разбиваем нашу первоначальную очень большую задачу на очень маленькие куски.
arr = Array.new(5000) {rand 10000} sorted_arr = arr.sort puts binary_search(sorted_arr, 50)
Вы можете видеть, как наш алгоритм нашел индекс в массиве, где были найдены элементы 50. Он не находил элемент каждый раз из-за моего теста.
Рекурсивно это выглядит так:
def binary_search_recursively(orig_arr, search_element, min_index = 0, max_index = orig_arr.length - 1) return nil if min_index > max_index midpoint = (max_index + min_index)/2 if orig_arr[midpoint] > search_element return binary_search_recuresively(orig_arr, search_element, min_index, midpoint - 1) elsif orig_arr[midpoint] < search_element return binary_search_recuresively(orig_arr, search_element, midpoint + 1, max_index) elsif orig_arr[midpoint] == search_element return midpoint end end
Когда я провел тот же тест, он вернул это:
Опять же, он смог найти индекс, в котором был засеян наш целевой элемент.
Как я уже писал ранее, бинарный поиск имеет временную сложность в наихудшем случае O(log(n)). Что очень быстро и эффективно для большого набора данных. Ruby может реализовать бинарный поиск с помощью встроенного метода Array#bsearch.
Все мы знаем о методе ruby find(), который использует постоянную временную сложность O(n). Это очень быстро! Для задач меньшего размера с целью поиска, близкой к началу массива. Несмотря на то, что O(log(n)) использует разделяй и властвуй со многими шагами, для очень большого размера задачи он выводит метод линейного времени find() из воды, когда данные большие, а целевой элемент ближе к концу.
Хотите увидеть, насколько быстр на самом деле бинарный поиск? Давайте посмотрим на тест-
require 'benchmark' range = (0..100_000_000) Benchmark.bm do |x| x.report(:find) {range.find {|number| number > 90_000_000 }} x.report(:bsearch) {range.bsearch {|number| number > 90_000_000}} end
Это результат-
Давайте запустим тест на диапазоне из 500 000 чисел!
require 'benchmark' range = (0..500_000_000) Benchmark.bm do |x| x.report(:find){range.find {|number| number > 450_000_000}} x.report(:bsearch){range.bsearch {|number| number > 450_000_000}} end
В этом сила логарифмической (n) временной сложности.