Недавно я изучал теорию Big O, чтобы улучшить время выполнения моих приложений и писать более эффективный код в целом. Одним из наиболее очевидных и первых примеров того, как соображения Big O могут помочь вашей среде выполнения, является сравнение линейного поиска. с помощью бинарного поиска.
Если вы не знакомы с теорией Big O, вот небольшое изложение:
Теория большого O может относиться как к времени выполнения, так и к пространству, но чаще всего связана со временем выполнения. Но что мы подразумеваем под временем выполнения? Один и тот же алгоритм, запущенный на двух разных машинах, может выполняться по-разному (представьте себе Mac с зеленым экраном и современный MacBook Pro). ). Таким образом, вместо того, чтобы измерять Big O буквальным количеством времени, которое требуется для запуска (которое зависит от компьютера к компьютеру), мы измеряем его количеством шагов, необходимых для выполнения данной задачи (что является с одного компьютера на другой).
Возьмем отсортированный массив чисел (его нужно отсортировать) в Ruby.
arr = (1..20).to_a
Если бы вы:
p arr => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
Итак, теперь у нас есть отсортированный массив. Теперь предположим, что мы хотели найти индекс числа 20 (оно имеет индекс 19). Самый простой способ поиска индекса числа в массиве — использовать простой линейный поиск (начиная с начала и проходя по каждому индексу, пока не найдете нужный индекс). номер, а затем возвращает этот индекс). В этом примере линейный поиск будет выглядеть так:
=> "count: 1" "count: 2" "count: 3" .... this just keeps incrementing until it hits count 20 ....... "count: 20" "Your item is at index: 19"
Поскольку 20 находится в самом конце массива, линейный поиск должен пройти через каждый индекс, прежде чем он достигнет 20 (то есть 20 шагов). В Big O мы бы назвали это O (N), потому что если в массиве есть N элементов, в худшем случае вам придется просмотреть весь массив (который имеет длину N). Для каждого элемента, который вы добавляете, вы добавляете дополнительный шаг. Это создает линейный график:
Теперь давайте посмотрим, как бинарный поиск решает ту же проблему. Помните, что для работы бинарного поиска массив необходимо отсортировать. Итак, возьмем тот же массив.
arr = (1..20).to_a p arr => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
"count 1" "middle is at index: 10" "count 2" "middle is at index: 15" "count 3" "middle is at index: 18" "count 4" "Your item is at index: 19" "middle is at index: 19" => 19
Прежде чем мы углубимся в код, давайте посмотрим на разницу в количестве. линейный поиск занял 20 шагов, чтобы найти 20 в массиве. Двоичный поиск занял 4 шага, чтобы найти 20 в массиве. Что?!?! Как это возможно? Это тот же объем данных, алгоритм возвращает тот же результат, но бинарный поиск намного быстрее! В нотации Big O мы говорим, что бинарный поиск — это O(logN). Что такое logN, спросите вы? Давайте посмотрим на код, и он будет иметь больше смысла.
- Обратите внимание, что существуют мин., средний и макс.. В начале метода min — первый индекс массива, а max — последний индекс массива. множество. middle находится в середине массива (независимо от того, насколько он велик или мал, потому что мы устанавливаем его с помощью:
middle = (min + max) / 2
По мере изменения минимального и максимального значений (следующие шаги) центральное значение будет постоянно переназначаться на (min + max) / 2.
2. Первое, что мы проверяем, оказавшись внутри цикла while, это если среднее — это число, которое мы ищем. Если да, то мы можем вернуть средний (поскольку это индекс искомого числа). Каждый раз, когда мы проходим новую итерацию цикла while, мы проверяем, является ли середина числом.
if array[middle] == item return middle end
3. Следующим шагом будет проверка, если массив[middle] меньше элемента. Если да, то вы можете разрезать массив пополам. Воу, воу, воу! Разрезать пополам?! да. Представьте, что вы ищете страницу в книге… скажем, страницу 100. Вы случайно открываете книгу, и это страница 75. Мы не собираемся тратить время на поиск страницы 100 перед страницей 75. Вместо этого вы только ищете для просмотра страниц выше 75. Вот почему нам нужна сортировка массива для выполнения бинарного поиска!
elsif array[middle] < item min = middle + 1 middle = (min + max) / 2
Теперь мы сбросили значение min на единицу больше, чем среднее (поскольку мы посмотрели на среднее, и оно было меньше элемента, мы знаем, что теперь минимальное значение должно быть больше среднего). Затем мы сбрасываем середину и запускаем цикл while заново.
4. Если бы массив[middle] был больше элемента, мы бы сделали обратное:
elsif array[middle] > item max = middle - 1 middle = (min + max) / 2
Здесь, если массив [средний] был больше элемента, все возможные правильные ответы меньше среднего. Поэтому мы устанавливаем max на единицу меньше среднего.
5. Мы продолжаем цикл while до тех пор, пока: 1) массив [middle] == item и мы не вернем средний (индекс) или 2) мы не сузим диапазон настолько, что min и max будут одним и тем же, и мы вернуть false (это означает, что мы не нашли номер, который вы искали).
Если мы вернемся к результатам запуска binary_search(20, array):
"count 1" "middle is at index: 10" "count 2" "middle is at index: 15" "count 3" "middle is at index: 18" "count 4" "Your item is at index: 19" "middle is at index: 19" => 19
Вы можете видеть, что для середины сначала установлено значение 10 (поскольку 10 — это индекс в середине массива из 20 индексов). Мы искали 20, но array[middle] == 11, а 11 меньше 20. Итак, здесь мы перемещаем min до 11 (индекс 11), а затем пересчитываем средний (min + max) / 2 == (11 + 20 ) / 2 == 15. Итак, теперь значение middle равно 15. Затем мы переходим к следующей итерации цикла while и продолжаем, пока не достигнем конца или не найдем элемент.
Каждый раз, когда мы проходим через итерацию цикла while, мы сокращаем наши возможные ответы вдвое! Это то, что дает бинарному поиску O(logN).
Обратите внимание, что количество шагов, необходимых для завершения бинарного поиска, уменьшается вдвое с каждым шагом (это потому, что мы сокращаем возможные ответы вдвое). Вот почему бинарный поиск с отсортированным массивом намного быстрее!
Теперь вы можете задаться вопросом: «Эй! Что, если бы мы искали 1?!? При линейном поиске вы бы нашли это за один шаг!» И на это я говорю: «Вы правы». В этом примере, если бы мы искали элемент == 1, бинарный поиск все равно потребовал бы 4 шагов, чтобы найти его, а линейный поиск — только один. Но если предположить, что вы не всегда ищете первый элемент в массиве, вы очень быстро опередите линейный поиск, используя бинарный поиск:
N Elements Max Linear Search Steps Max Binary Search Steps 8 8 3 16 16 4 32 32 5 1024 1024 10
И это подводит нас к важному моменту, касающемуся теории большого О. Теория большого O не касается небольших данных. При сегодняшних современных вычислительных мощностях разница во времени между 1 и 4 шагами незначительна. Теория большого O очень связана с масштабированием данных. Заметьте выше, что 1024 элемента займут для линейного поиска максимум 1024 шага (поскольку, возможно, придется идти до конца), а для бинарного поиска — максимум 10 шагов (потому что после первой итерации останется только 512 вариантов и скоро). Эта способность масштабироваться по мере увеличения данных является силой бинарного поиска, и Big O отражает это, отмечая это как O (logN).
Надеюсь, это поможет вам, когда вы отправитесь в мощный мир нотации Big O! Проверьте мой личный веб-сайт, учетную запись LinkedIn и учетную запись GitHub ниже!
Удачного кодирования!
-Джейми
https://ronincode.github.io/ ←Персональный сайт
https://www.linkedin.com/in/jamie-mackillop/ ← LinkedIn
https://github.com/roninCode ← GitHub
