Datastrukturer och algoritmer - Tidskomplexitet

Hej,

Jag försöker lösa en fråga som lyder:

En algoritm med logaritmisk tidskomplexitet exekverades för n = 10000 vilket tog 6ms. Vid en annan exekvering tog det istället 3ms. Hur många element förväntas arrayen ha innehållit?

I kursen utgår vi från formeln T(n) = c * f(n) där f(n) är tillväxtfunktionen, c är en konstant och T(n) är körtiden. Svaret på frågan är 100 fast jag förstår inte hur jag ska komma fram till det. Ska jag använda basen 2 eller 10?

Tacksam för tips och hjälp om hur jag löser frågan.

Basen spelar ingen roll om man gör förenklingen att komplexitetsfunktionen är en ren logaritm.

Antar jag att basen är $e$ , dvs att $f(n) = C\ln(n)$ så har jag att konstanten är kvoten av funktionen värde och logaritmen av n

$C = f(n) / \ln(n)$

Varför informationen i uppgiften ger att

$\frac{6}{\ln(10000)} = \frac{3}{\ln(n)}$

$\ln(n) = 0.5 \ln(10000)$

$n = e^{0.5 \ln(10000)} = (e^{\ln(10000)})^{0.5} = 10000^{0.5} = \sqrt{10000} = 100$

I ett delsteg tar exp och ln ut varandra och det kommer de att göra oavsett vilken bas vi har. Testa att lösa problemet i bas 2, bas 10, bas 25, och du får alltid samma svar.

Rent allmänt:

Om en logaritmisk funktions värde ska förändras med en faktor faktor p så måste argumentet höjas upp med $p$ för att åstadkomma det. Det är en rak tillämpning av logaritmlagen

$\ln(x^p) = p \ln(x)$

Men denna lag gäller oavsett bas. Samma sak för

$\log_2(x^p) = p \log_2(x)$

Egentligen behöver man inte lösa ekvationer alls om man förstår logaritmlagarna.

Konkret:

Om en algoritm med logaritmisk komplexitet tar Y ms för indata med storlek X så kommer indata med storlek X^p at kräva en tidsåtgång på ungefär pY ms.

Detta är funktionellt vad logaritmisk komplexitet är. Om man ökar indatans storlek med exponenten p så ökar tidsåtgången med en faktor p.

SeriousCephalopod skrev:
Basen spelar ingen roll om man gör förenklingen att komplexitetsfunktionen är en ren logaritm.

Antar jag att basen är $e$ , dvs att $f(n) = C\ln(n)$ så har jag att konstanten är kvoten av funktionen värde och logaritmen av n

$C = f(n) / \ln(n)$

Varför informationen i uppgiften ger att

$\frac{6}{\ln(10000)} = \frac{3}{\ln(n)}$

$\ln(n) = 0.5 \ln(10000)$

$n = e^{0.5 \ln(10000)} = (e^{\ln(10000)})^{0.5} = 10000^{0.5} = \sqrt{10000} = 100$

I ett delsteg tar exp och ln ut varandra och det kommer de att göra oavsett vilken bas vi har. Testa att lösa problemet i bas 2, bas 10, bas 25, och du får alltid samma svar.

Rent allmänt:

Om en logaritmisk funktions värde ska förändras med en faktor faktor p så måste argumentet höjas upp med $p$ för att åstadkomma det. Det är en rak tillämpning av logaritmlagen

$\ln(x^p) = p \ln(x)$

Men denna lag gäller oavsett bas. Samma sak för

$\log_2(x^p) = p \log_2(x)$

Egentligen behöver man inte lösa ekvationer alls om man förstår logaritmlagarna.

Konkret:

Om en algoritm med logaritmisk komplexitet tar Y ms för indata med storlek X så kommer indata med storlek X^p at kräva en tidsåtgång på ungefär pY ms.

Detta är funktionellt vad logaritmisk komplexitet är. Om man ökar indatans storlek med exponenten p så ökar tidsåtgången med en faktor p.

Tusen tack!

Svara