4 svar
41 visningar
lemma57 är nöjd med hjälpen!
lemma57 44
Postad: 23 maj 2019

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å 0,3log(2000) μs. 

På 0,6 μs hinner vi göra 0,60,3log(2000) = 2×log(2000) delningar. 

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

log(n) = 2×log(2000)

n=20002 = 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.

Laguna 4992
Postad: 23 maj 2019

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.

Affe Jkpg 4626
Postad: 23 maj 2019

Ett annat sätt att se det...

Säg att det var 2048 = 211 element.

Jag kan väl tycka att man ska resonera om 2n 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.

2224.2 miljoner element

lemma57 44
Postad: 23 maj 2019 Redigerad: 23 maj 2019
Affe Jkpg skrev:

Ett annat sätt att se det...

Säg att det var 2048 = 211 element.

Jag kan väl tycka att man ska resonera om 2n 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.

2224.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?

Laguna 4992
Postad: 24 maj 2019
lemma57 skrev:
Affe Jkpg skrev:

Ett annat sätt att se det...

Säg att det var 2048 = 211 element.

Jag kan väl tycka att man ska resonera om 2n 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.

2224.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 Avbryt
Close