Till KTH:s startsida Till KTH:s startsida

Körtider


Antal indata är \(n\)
Vi kallar den sökta körtiden \(x\)

1. Linjär tid innebär att T(n)=kn

För \(n=100\) tar algoritmen 0.5 ms, alltså
\(k*100 = 0.5\)
För \(n=500\) tar algoritmen x ms, alltså
\(k*500 = x\)
Löser vi ut \(x\) får vi 2.5 ms dvs 5 gånger så lång tid.

2. O(nlogn) innebär att T(n)=knlogn

För \(n=100\) tar algoritmen 0.5 ms, alltså
\(k*100*\log_{}100 = 0.5\)
För \(n=500\) tar algoritmen x ms, alltså
\(k*500*\log_{}500 = x\)
\(x=0.5*\frac{500\log_{}500}{100\log_{}100}\)
Löser vi ut \(x\) får vi 3.4 ms dvs ca 6 gånger så lång tid.

3. Kvadratisk tid innebär att T(n)=kn2

För \(n=100\) tar algoritmen 0.5 ms, alltså
\(k*100^{2} = 0.5\)
För \(n=500\) tar algoritmen x ms, alltså
\(k*500^{2} = x\)
\(x=0.5*\frac{500^{2}}{100^{2}}\)
Löser vi ut \(x\) får vi 12.5 ms dvs 25 gånger så lång tid.

4. Kubisk tid innebär att T(n)=kn3

För \(n=100\) tar algoritmen 0.5 ms, alltså
\(k*100^{3} = 0.5\)
För \(n=500\) tar algoritmen x ms, alltså
\(k*500^{3} = x\)
\(x=0.5*\frac{500^{3}}{100^{3}}\)
Löser vi ut \(x\) får vi 62.5 ms dvs 125 gånger så lång tid.