Време за изпълнение на двоично търсене

Знаем, че линейно търсене в масив от $n$n елемента може да отнеме най-много $n$n предположения. Може би вече интуитивно достигна до извода, че за двоичното търсене са необходими по-малко на брой отгатвания. Даже може би усети, че разликата между броя отгатвания в най-лошия случай за линейното и двоичното търсене става все по-зашеметяваща с увеличаването на дължината на масива. Нека видим как да анализираме максималният брой предположения, който двоичното търсене може да направи.

Основната идея е, че когато двоичното търсене прави грешно предположение, частта от масива, която съдържа "разумните" предположения, намалява най-малко наполовина. Ако разумната част има 32 елемента, то едно неправилно предположение я оставя с най-много 16. Двоичното търсене намалява наполовина размера на разумната част всеки път, когато направи грешно предположение.

Ако започнем с масив с дължина 8, тогава неправилните предположения ще намалят броя на логичните позиции на 4, после на 2 и накрая на 1. След като разумната част съдържа само един елемент, няма да има повече предположения; предположението за частта с един елемент е или вярно или грешно и алгоритъмът приключва работа. Така че за масив с дължина 8 двоичното търсене се нуждае от най-много 4 проверки.

Какво мислиш, че ще се случи с масив от 16 елемента? Ако предположиш, че първото предположение ще елиминира поне 8 елемента, и така остави най-много 8 възможни, значи започваш да схващаш картинката. Затова за 16 елемента са ни необходими най-много 5 опита.

Вече сигурно сте забелязали модела. Всеки път, когато увеличим два пъти размера на масива, ние трябва да използваме още най-много едно предположение. Да предположим, че ни трябват най-много $m$m проверки за масив с дължина $n$n. Тогава за масив с дължина $2n$2, n, първото предположение намалява размера разумна част от масива до $n$n, и ни трябват най-много $m$m предположения, за да открием търсената стойност, което ни дава най-много $m + 1$m, plus, 1 проверки.

Да разгледаме основния случай с масив с дължина $n$n. Можем да представим броя отгатвания, в най-лошия случай, като "броя пъти, които можем повторно да преполовим, като започнем от $n$n, докато стигнем до стойност 1, плюс едно". Но това е много неудобно за изписване.

За щастие, има математическа функция, която връща точно броя пъти, които повторно можем да преполовяваме от $n$n, докато стигнем до 1: логаритъм от $n$n при основа 2. Това често се изписва като $\log_2 n$log, start base, 2, end base, n, но можеш да го видиш написано и така $\lg n$\lg, n в текстове по компютърни науки. (Искаш ли да си преговориш логаритмите? Научи повече тук.)

Ето една таблица, която показва логаритмите при основа 2 за различни стойности на $n$n:

Можем да покажем тази таблица и като графика:

Ако приближим графиката за по-малки стойности на n:

Логаритмичната функция расте много бавно. Логаритмите са обратното на експоненциалните функции, които растат много бързо, така че ако $\log_2 n = x$log, start base, 2, end base, n, equals, x, то $n = 2^x$n, equals, 2, start superscript, x, end superscript. Например, тъй като $\log_2 n 128 = 7$log, start base, 2, end base, n, 128, equals, 7, знаем, че $2 ^ 7 = 128$2, start superscript, 7, end superscript, equals, 128.

Така лесно можем да изчислим времето за изпълнение на алгоритъм за двоично търсене за $n$n, което е точно степен на 2. Ако $n$n е 128, на двоичното търсене ще му отнеме най-много 8 ($\log_2 128 + 1$log, start base, 2, end base, 128, plus, 1) отгатвания.

Ами ако $n$n не е степен на двойката? В този случай можем да потърсим най-близките степени на двойката. За един масив с дължина 1000, най-близката степен на двойката е 512, което е равно на $2^{9}$2, start superscript, 9, end superscript. Така можем да предположим, че $\log_2 1000$log, start base, 2, end base, 1000 е число по-голямо от 9 и по-малко от 10, или да използваме калкулатор, за да изчислим, че е равно на около 9,97. Като прибавим едно, получаваме 10,97. Когато имаме десетична дроб, закръгляме надолу, за да открием точния брой отгатвания. Следователно за масив от 1000 елемента, на двоичното търсене ще са му нужни най-много 10 отгатвания.

За звездния каталог Tycho-2 с 2 539 913-те звезди, най-близката степен на 2 (закръглена надолу) е $2^{21}$2, start superscript, 21, end superscript (което е 2 097 152), така че ще ни трябват най-много 22 отгатвания. Много по-добре от линейното търсене!

Сравни $n$n vs $\log _{2} n$log, start base, 2, end base, n по-долу:

В следващия урок ще видим как компютърните специалисти характеризират времето за работа на линейното и двоичното търсене, като използват означение, което отделя най-важната част от работното време и "изхвърля" по-маловажните неща.

Това съдържание е резултат от съвместната дейност на преподавателите по Компютърни науки в Дартмут Thomas Cormen и Devin Balkcom, както и на екипа по компютърни науки на Кан Академия. Съдържанието е лицензирано CC-BY-NC-SA.