Двоично търсене + главна теорема

Binary Search Master Theorem

Дихотомия: двоично търсене

Бинарното търсене е подходящо, когато количеството данни е голямо, но данните първо трябва да бъдат сортирани. Основната идея е: (да предположим, че интервалът на търсения масив е масив [нисък, висок])

Определете средната позиция K (2) на интервала и сравнете търсената стойност T с масив [k]. Ако са равни, търсенето се връща успешно в тази позиция, в противен случай се определя нова област на търсене и бинарното търсене продължава.

Площта се определя, както следва: a.array [k]> T От реда на масива знаем, че масивът [k, k + 1, ……, висок]> T, така че новият интервал е масив [нисък, ... …, K-1] b.array [k]

Всеки път, когато търсенето се сравнява с междинната стойност, може да се определи дали търсенето е успешно или не, текущият интервал на търсене ще бъде намален наполовина, ако е неуспешен, и рекурсивното търсене е достатъчно. Сложността във времето е: O (log2n)

Едномерен масив:

Половин търсене] Ако има група от числа 3, 12, 24, 36, 55, 68, 75, 88 за проверка на дадената стойност 24. Три променливи отпред, средата, края могат да бъдат настроени да сочат към горната граница, средата и Долна граница, средна = (предна + крайна) / 2.

1. Започнете с пред = 0 (сочи към 3), край = 7 (сочи към 88), след това средата = 3 (сочи към 36).

Тъй като a [mid]> x, трябва да се търси през първата половина.

2. Нека новият край = mid-1 = 2, а предният = 0 непроменен, след това новият mid = 1. По това време x> a [mid], така че не забравяйте да търсите през втората половина.

3. Оставете новия фронт = mid + 1 = 2 и end = 2 непроменен, след това новия mid = 2, в този момент a [mid] = x, търсенето е успешно. Ако числото, което искате да намерите, не е число в последователността, например x = 25, когато е направено третото решение, x> a [mid], съгласно горното правило, нека front = mid + 1, че е, front = 3 и се появява front> end, Това означава, че търсенето е неуспешно. Пример: Намерете данните x, въведени от потребителя в подреден масив от N елемента.

Алгоритъмът е както следва:

1. Определете диапазона на търсене front = 0, end = N-1 и изчислете средния срок mid = (front + end) / 2.

2. Ако [mid] = x или front> = end, прекратете търсенето по друг начин, продължете надолу.

3. Ако [mid] x, това означава, че стойността на елемента, който трябва да се търси, може да бъде само в диапазона, по-малък от средния елемент, след това задайте стойността на mid-1 до края, преизчислете mid и преминете към стъпка 2.

Дихотомия нерекурсивна

function binarySearch(arr,key){ Var low=0 //Minimum index value of array Var high=arr.length-1 //Maximum index value of array while(lowarr[mid]){ low=mid+1 }else{ high=mid-1 } } Return -1 //In the case of low>high, in this case the value of key is greater than the value of the largest element in arr or the value of key is less than the value of the smallest element in arr }

Дихотомна рекурсия

function binarySearch(arr,low,high,key){ if(low>high){return -1} var mid=Math.floor((low+high)/2) if(key==arr[mid]){ return mid }else if(key

Сложността във времето на дихотомията е O (logn),

N * （1/2） ^ x = 1

Под скалата на N броят на изпълненията е x, докато крайната хипотеза е 1, така че сложността на времето на дихотомията е O (log2n), а основата е 2.

Разбира се, можем да използваме теорията на Учителя, за да видим дихотомичната рекурсия

T (n) = T (n / 2) + O (1)

Дихотомията е:

{Вземаме проблема с мащаба n} -> {Проблем с мащаба n / 2 + [някои допълнителни изчисления -> O (1)]}

Според формулата на теоремата на Учителя бързо получаваме

Така че T (n) = O (logn)

---

Магистърска теорема

Каква е теоремата на Учителя и за какво служи?

Теоремата на Учителя се използва за бързо получаване на сложността във времето на рекурсивния алгоритъм.

от Baidu Encyclopedia

По-долу е съдържанието на основната теорема (екранна снимка от статия на този сайт, забравих). Ако в бъдеще срещнете рекурсивен T (n), можете бързо да получите времевата сложност на рекурсията директно според следното

В интернет има много статии, в които се казва, че a> 1 това не е строго, а може да бъде = 1Последното n ^ d е допълнителното изчисление в нашата рекурсия. Обикновено сложността на времето при това изчисление е O (1)