1
Beräkna o(n log n)
Postat av Låst Konto 13442 den 19 Juli 2014, 00:30
21 kommentarer · 595 träffar
Hej, pysslar med lite datastrukturer. Undrar.
Jag försöker lista ut här hur man beräknar binära sökningar, genom komplexitetsberäkningar. Och då är det en specifik som jag undrar.
O(n log n) is n times the logarithm base 2 of n.
Motsvarar det då enligt matematiken. Begreppet n motsvarar ju input, det värdet som ska passeras in. Och i och med att det är en sökning så är det också det input värdet jag vill få.
Så, om jag följer detta rent matematiskt så ska jag enligt min dumma översättning få:
n * (2 förhöjt N) =
log2 1024 = 10 steg om jag letar efter 1024 elements i en lista.
Vilket blir, n gånger logaritmen bas 2n. Så, för att sortera 10 items så går det 30 gånger.
Så för att räkna ut hur många gånger jag räknar 10 element så måste jag alltså ta log 2_10 ?då jag definerade att n var 10.
Så min fråga är:
Så på mindre mängd element, om det tar 30 steg för att räkna ut 10, är det då smart att använda sig av en sådan sökningsalgoritm? :D
Jag försöker lista ut här hur man beräknar binära sökningar, genom komplexitetsberäkningar. Och då är det en specifik som jag undrar.
O(n log n) is n times the logarithm base 2 of n.
Motsvarar det då enligt matematiken. Begreppet n motsvarar ju input, det värdet som ska passeras in. Och i och med att det är en sökning så är det också det input värdet jag vill få.
Så, om jag följer detta rent matematiskt så ska jag enligt min dumma översättning få:
n * (2 förhöjt N) =
log2 1024 = 10 steg om jag letar efter 1024 elements i en lista.
Vilket blir, n gånger logaritmen bas 2n. Så, för att sortera 10 items så går det 30 gånger.
Så för att räkna ut hur många gånger jag räknar 10 element så måste jag alltså ta log 2_10 ?då jag definerade att n var 10.
Så min fråga är:
Så på mindre mängd element, om det tar 30 steg för att räkna ut 10, är det då smart att använda sig av en sådan sökningsalgoritm? :D
