hoe de complexiteit van binaire zoekopdrachten te berekenen

Ik hoorde iemand zeggen dat aangezien binair zoeken de invoer die nodig is om te zoeken halveert, het log(n)-algoritme is. Omdat ik geen wiskundeachtergrond heb, kan ik me er niet mee inleven. Kan iemand het wat nader toelichten? Heeft het iets te maken met de logaritmische reeks?

Antwoord 1, autoriteit 100%

Hier een meer wiskundige manier om het te zien, hoewel niet echt ingewikkeld. IMO veel duidelijker als informele:

De vraag is, hoe vaak kun je N door 2 delen totdat je 1 hebt? Dit is in wezen zeggen, doe een binaire zoekopdracht (de helft van de elementen) totdat je het hebt gevonden. In een formule zou dit dit zijn:

1 = N / 2^x

vermenigvuldigen met 2^x:

2^x= N

doe nu het log₂:

log₂(2^x)    = log₂N
x * log₂(2) = log₂N
x * 1         = log₂N

dit betekent dat je log N keer kunt delen totdat je alles hebt gedeeld. Dat betekent dat je log N moet delen (“doe de binaire zoekstap”) totdat je je element hebt gevonden.

Antwoord 2, autoriteit 6%

Voor binair zoeken,
T(N) = T(N/2) + O(1) // de herhalingsrelatie

Pas de Masters-stelling toe voor het berekenen van Runtime-complexiteit van recursierelaties:
T(N) = aT(N/b) + f(N)

Hier, a = 1, b = 2
=> log (a grondtal b) = 1

ook hier f(N) = n^c log^k(n) //k = 0 & c = log (een grondtal b)

Dus, T(N) = O(N^c log^(k+1)N) = O(log(N))

Bron: http://en.wikipedia.org/wiki/Master_theorem

Antwoord 3, autoriteit 4%

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

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

Zet de waarde van The(n/2) hierboven zodat T(n)=T(n/4)+1+1
.
.
.
.
T(n/2^k)+1+1+1…..+1

=T(2^k/2^k)+1+1….+1 tot k

=T(1)+k

Zoals we 2^k=n hebben genomen

K = log n

Dus tijdscomplexiteit is O(log n)

Antwoord 4, autoriteit 3%

Het halveert de zoektijd niet, dat zou het geen log(n) maken. Het verlaagt het logaritmisch. Denk hier even over na. Als u 128 vermeldingen in een tabel had en lineair naar uw waarde moest zoeken, zou het waarschijnlijk gemiddeld ongeveer 64 vermeldingen kosten om uw waarde te vinden. Dat is n/2 of lineaire tijd. Met een binaire zoekopdracht elimineert u de helft van de mogelijke items per iteratie, zodat er maximaal 7 vergelijkingen nodig zijn om uw waarde te vinden (loggrondslag 2 van 128 is 7 of 2 tot de macht 7 is 128). de kracht van binair zoeken.

Antwoord 5

De tijdscomplexiteit van het binaire zoekalgoritme behoort tot de klasse O(log n). Dit wordt grote O-notatiegenoemd. De manier waarop u dit moet interpreteren is dat de asymptotische groei van de tijd die nodig is om de functie uit te voeren gegeven een invoerset van grootte n niet groter zal zijn dan log n.

Dit is gewoon formeel wiskundig jargon om uitspraken te kunnen bewijzen, enz. Het heeft een heel duidelijke uitleg. Wanneer n erg groot wordt, zal de log n-functie groter worden dan de tijd die nodig is om de functie uit te voeren. De grootte van de “invoerset”, n, is slechts de lengte van de lijst.

Simpel gezegd, de reden dat binair zoeken in O(log n) is, is dat het de invoerset in elke iteratie halveert. Het is gemakkelijker om erover na te denken in de omgekeerde situatie. Op x iteraties, hoe lang kan het binaire zoekalgoritme bij max onderzoeken? Het antwoord is 2^x. Hieruit kunnen we zien dat het omgekeerde is dat het binaire zoekalgoritme gemiddeld log2 n iteraties nodig heeft voor een lijst met lengte n.

Als de reden waarom het O(log n) is en niet O(log2 n), is dat omdat het simpelweg opnieuw wordt gezegd: het gebruik van de grote O-notatieconstanten telt niet.

Antwoord 6

Hier is wikipedia-item

Als je kijkt naar de eenvoudige iteratieve aanpak. Je elimineert gewoon de helft van de elementen waarnaar moet worden gezocht totdat je het element hebt gevonden dat je nodig hebt.

Hier is de uitleg van hoe we tot de formule komen.

Stel in eerste instantie dat je N aantal elementen hebt en wat je dan doet is
⌊N/2⌋ als eerste poging. Waar N de som is van de ondergrens en de bovengrens. De eerste tijdswaarde van N zou gelijk zijn aan (L + H), waarbij L de eerste index (0) is en H de laatste index van de lijst die u zoekt. Als je geluk hebt, zal het element dat je probeert te vinden in het midden staan [bijv. Zoek je 18 in de lijst {16, 17, 18, 19, 20} dan bereken je ⌊(0+4)/2⌋ = 2 waarbij 0 de ondergrens is (L – index van het eerste element van de array) en 4 is de bovengrens (H – index van het laatste element van de array). In bovenstaand geval L = 0 en H = 4. Nu is 2 de index van het element 18 dat je zoekt gevonden. Bingo! Je hebt het gevonden.

Als de casus een andere array was{15,16,17,18,19} maar je nog steeds naar 18 zocht, dan zou je geen geluk hebben en zou je eerste N/2 doen (dat is ⌊(0+ 4)/2⌋ = 2 en realiseer je dan dat element 17 bij de index 2 niet het getal is dat je zoekt. Nu weet je dat je bij je volgende poging om iteratief te zoeken niet naar ten minste de helft van de array hoeft te zoeken manier. Uw zoekinspanning wordt gehalveerd. Dus eigenlijk zoekt u niet de helft van de lijst met elementen die u eerder hebt gezocht, elke keer dat u het element probeert te vinden dat u bij uw vorige poging niet kon vinden.

Dus in het slechtste geval zou

[N]/2 + [(N/2)]/2 + [((N/2)/2)]/2…..

dat wil zeggen:
N/2¹+ N/2²+ N/2³+….. + N/2^{x< /sup>…..}

totdat u klaar bent met zoeken, waarbij het element dat u probeert te vinden zich aan het einde van de lijst bevindt.

Dat laat zien dat het slechtste geval is wanneer u N/2^xbereikt, waarbij x zodanig is dat 2^x= N

In andere gevallen N/2^xwaarbij x zodanig is dat 2^x< N
De minimumwaarde van x kan 1 zijn, wat het beste is.

Omdat wiskundig gezien het slechtste geval is wanneer de waarde van
2^x= N
=> log₂(2^x) = log₂(N)
=> x * log₂(2) = log₂(N)
=> x * 1 = log₂(N)
=> Meer formeel ⌊log₂(N)+1⌋

Antwoord 7

⌊log₂(n) + 1⌋ is het maximale aantal vergelijkingen dat nodig is om iets te vinden in een binaire zoekopdracht. Het gemiddelde geval maakt ongeveer log₂(n) – 1 vergelijkingen. Hier is meer informatie:

http://en.wikipedia.org/wiki/Binary_search#Performance

Antwoord 8

Stel dat de iteratie in Binary Search eindigt na kiteraties.
Bij elke iteratie wordt de array door de helft gedeeld. Dus laten we zeggen dat de lengte van de array bij elke iteratie n . is
Bij iteratie 1,

Length of array = n

Bij iteratie 2,

Length of array = n⁄2

Bij iteratie 3,

Length of array = (n⁄2)⁄2 = n⁄22

Daarom, na Iteratie k,

Length of array = n⁄2k

Ook weten we dat na
Na k delingen, de lengte van de array wordt 1
Daarom

Length of array = n⁄2k = 1
=> n = 2k

Logfunctie aan beide kanten toepassen:

=> log2 (n) = log2 (2k)
=> log2 (n) = k log2 (2)
As (loga (a) = 1)

Daarom,

As (loga (a) = 1)
k = log2 (n)

Vandaar dat de tijdscomplexiteit van binair zoeken is

log2 (n)

Antwoord 9

Een binaire zoekopdracht werkt door het probleem herhaaldelijk in tweeën te delen, ongeveer als volgt (details weggelaten):

Voorbeeld op zoek naar 3 in [4,1,3,8,5]

1. Bestel uw lijst met items [1,3,4,5,8]
2. Kijk naar het middelste item (4),
   • Als het is wat je zoekt, stop dan
   • Als het groter is, kijk dan naar de eerste helft
   • Als het minder is, kijk dan naar de tweede helft
3. Herhaal stap 2 met de nieuwe lijst [1, 3], zoek 3 en stop

Het is een twee-zoekopdracht wanneer je het probleem in 2 deelt.

De zoekopdracht vereist alleen log2(n) stappen om de juiste waarde te vinden.

Ik zou Inleiding tot algoritmenaanraden als je meer wilt weten over algoritmische complexiteit.

Antwoord 10

Omdat we een lijst elke keer halveren, hoeven we alleen maar te weten in hoeveel stappen we 1 krijgen als we doorgaan met het delen van een lijst door twee. In de onderstaande berekening geeft x het aantal keren aan dat we een lijst verdelen totdat we één element krijgen (in het ergste geval).

1 = N/2x

2x = N

Log2 maken

log2(2x) = log2(N)

x*log2(2) = log2(N)

x = log2(N)

Antwoord 11

T(N) = T(N/2) + 1

T(N) = T(N/2) + 1 = (T(N/4) + 1)+ 1

…

T(N) = T(N/N) + (1 + 1 + 1 +… + 1) = 1 + logN (basis 2 log) = 1 + logN

Dus de tijdscomplexiteit van binair zoeken is O(logN)

Antwoord 12

ok see this
for(i=0;i<n;n=n/2)
{
i++;
}
1. Suppose at i=k the loop terminate. i.e. the loop execute k times.
2. at each iteration n is divided by half.
2.a n=n/2                   .... AT I=1
2.b n=(n/2)/2=n/(2^2)
2.c n=((n/2)/2)/2=n/(2^3)....... aT I=3
2.d n=(((n/2)/2)/2)/2=n/(2^4)
So at i=k , n=1 which is obtain by dividing n  2^k times
n=2^k
1=n/2^k 
k=log(N)  //base 2

Antwoord 13

Laat me het jullie allemaal gemakkelijk maken met een voorbeeld.

Laten we voor de eenvoud aannemen dat er 32 elementen in een array zijn in de gesorteerde volgorde van waaruit we een element zoeken met behulp van binair zoeken.

1 2 3 4 5 6 … 32

Stel dat we zoeken naar 32.
na de eerste iteratie blijven we achter met

17 18 19 20 …. 32

na de tweede iteratie houden we

. over

25 26 27 28 …. 32

na de derde iteratie houden we

. over

29 30 31 32

na de vierde iteratie houden we

. over

31 32

In de vijfde iteratie vinden we de waarde 32.

Dus als we dit omzetten in een wiskundige vergelijking, krijgen we

(32 X (1/2⁵)) = 1

= & gt; n x (2 ^{-k ) = 1}

= & gt; (2 ^{K ) = N}

= & gt; k log ₂ 2 = log ₂ n

= & gt; k = log ₂ n

Vandaar het bewijs.

Antwoord 14

Hier is de oplossing met behulp van de Master THEOREM, met leesbare latex.

Voor elk recidief in de herhalingrelatie voor binaire zoekopdracht, converteren wij het probleem in één subprobleem, met runtime t (N / 2). Daarom:

Vervanging in de Master Theorem, krijgen we:

Nu, omdat is 0 en f (n) is 1, we kunnen het tweede geval van de Master THEOREM gebruiken omdat:

Dit betekent dat: