В Части 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) временной сложности.