Tidskomplexitet - binary search

Hej, jag försöker räkna ut detta;

Anta att binary search i en sorterad array med n=2000 element tar 0,3 mikrosekunder i värsta fallet. Hur stort n klarar algoritmen då på 0,6 mikrosekunder?

Binary search har alltså tidskomplexitet O(log n). Hur jag räknar med detta är dock oklart. Jag har aldrig räknat eller läst om tidskomplexitet, så har försökt googla lite och kommit fram till detta:

Som jag har förstått så anger log(n) hur många gånger vi måste dela vår array med 2 innan vi hittar rätt element. Om vi har n=2000 element så måste vår array delas log(2000) gånger. Detta tar 0,3 μs, en delning tar alltså $\frac{0, 3}{\log (2000)}$ μs.

På 0,6 μs hinner vi göra $\frac{0, 6}{\frac{0, 3}{\log (2000)}} = 2 \times \log (2000)$ delningar.

Då ställer jag upp en ekvation för vilket n som kräver $2 \times \log (2000)$ delningar:

$\log (n) = 2 \times \log (2000)$

$n = 2000^{2} = 4 000 000$ element.

Detta svar känns ju dock ganska orimligt.. På nåt sätt har antal element ökat drastiskt istället för tiden. Men jag vet inte vad som är fel? Kan man inte anta att varje delning tar lika lång tid?

Tack på förhand.

Jag tror du har fått rätt svar. Visserligen ska man börja tänka på om allt det där får plats i arbetsminnet (det gör det förstås på en modern dator, men det är inte säkert att alla data faktiskt ligger redo i minnet), men det sa uppgiften ingenting om.

Ett annat sätt att se det...

Säg att det var 2048 = 2¹¹ element.

Jag kan väl tycka att man ska resonera om 2ⁿ med talet n som ett heltal.
I värsta fallet behöver man då använda 11 binär val även för 2000 element, vilket tar på 0.3 $μ$ s. 22 binära val tar då 0.6 $μ$ s.

$2^{22} \approx 4.2$ miljoner element

Affe Jkpg skrev:
Ett annat sätt att se det...
Säg att det var 2048 = 2¹¹ element.
Jag kan väl tycka att man ska resonera om 2ⁿ med talet n som ett heltal.
I värsta fallet behöver man då använda 11 binär val även för 2000 element, vilket tar på 0.3 $μ$ s. 22 binära val tar då 0.6 $μ$ s.
$2^{22} \approx 4.2$ miljoner element

Tack för svar!

Men verkar det inte orimligt att antal element ökar så drastiskt, när tiden bara dubbleras? Jag tänkte snarare att det skulle bli tvärtom. Edit: jag kan ha blandat ihop det, jag trodde O(logn) var något negativt, att tiden skulle öka väldigt mycket med bara en liten ökning i antal element, men det verkar vara tvärtom?

lemma57 skrev:
Affe Jkpg skrev:
Ett annat sätt att se det...
Säg att det var 2048 = 2¹¹ element.
Jag kan väl tycka att man ska resonera om 2ⁿ med talet n som ett heltal.
I värsta fallet behöver man då använda 11 binär val även för 2000 element, vilket tar på 0.3 $μ$ s. 22 binära val tar då 0.6 $μ$ s.
$2^{22} \approx 4.2$ miljoner element
Tack för svar!
Men verkar det inte orimligt att antal element ökar så drastiskt, när tiden bara dubbleras? Jag tänkte snarare att det skulle bli tvärtom. Edit: jag kan ha blandat ihop det, jag trodde O(logn) var något negativt, att tiden skulle öka väldigt mycket med bara en liten ökning i antal element, men det verkar vara tvärtom?

Binärsökning är mycket snabb. Man skyfflar ju inte omkring de halverade datalistorna eller ens tittar på de mesta av dem, utan pekar bara ut gränserna för var det sökta elementet kan finnas.

Svara

Visa senaste svar