Algoritm Tids Kompliexitet – Java – Nyheder for rigtige nørder

#1 - Windcape
18. mar. 2009 23:03

Hej

I forbindelse med noget materiale omkring tidskomplexitet af algoritmer, har jeg følgende eksempel:


int result = 0;
for(int i = 0; i<=n ;i++ )
{
result = result+i;
}

Jeg skal så at kunne udregne værdien af T(n) , hvor hver primitiv operation tæller for en.

Her er hvad jeg er nået frem til


// Initialization, Assignement = 2
int result = 0;

// Initialization, Assignement, (Comparision) * n, (Arithmetic, Assignement) * n = 2 + 1n + 2n = 3n + 2
for(int i = 0; i<=n ;i++ )
{
// (Assignement, Arithmetic) * n = 2n
result = result+i;
}

Dvs.:


2 + 3n + 2 + 2n = 5n + 4

Men ifølge mit materiale er svaret:


1 + 1 + 3*(n+2) + (n+1)+ 4*(n+1) = 8n + 13

Hvilket jeg altså ikke kan se hvorfor. F.eks. hvis man ser på selve for(;;) delen af koden, så defines komplexiteten som

3(n+2) istedet for 3n+2

Dette kan kun være korrekt hvis man assumere at int i = 0; bliver redefineret for hver iteration, hvilket jo ikke er korrekt i Java (eller for den sags skyld ethvert andet sprog).

Nogle ideer til hvad det er jeg misser?

#2 - arne_v
19. mar. 2009 00:07

Uden at have en helt præcis definition af hvad primitive operationer er, så er det umuligt at sige.

Jeg får f.eks. løkken til 7n via:

loop:
compare i to n
if greater than jump to endloop
calculate result + i
assign to result
calculate i + 1
assign to i
unconditionally jump to loop
endloop:

#3 - arne_v
19. mar. 2009 00:09

Iøvrigt er jeg tilbøjelig til at betragte hele beregning som spild af tid.

Som oftest vil man kun have brug for den overordnede kompleksitet og den er O(n) uanset hvad.

Og hvis man endelig vil ned i detaljerne, så kan man ikke bare betragte alle operationer som ens.

#4 - Windcape
19. mar. 2009 00:18

Mit materiale definere det som


Assignment af værdi til variabel
Metode kald
Aritmetisk operation (+ - * osv.)
Sammenligning af to værdier
Indeksering i array
Følge objekt reference
Returnere fra metodekald

#5 - Windcape
19. mar. 2009 00:25

arne_v (3) skrev:
Som oftest vil man kun have brug for den overordnede kompleksitet og den er O(n) uanset hvad.

Det er nok rigtigt.

Men hvis det ikke er præcist defineret hvad der er en instruks hvordan kan man så udregne O(n) alligevel ?

#6 - Windcape
19. mar. 2009 00:27

Og så lige for at se om jeg har forstået det korrekt.

Hvis den første kode er O(n) så er følgende kode O(n/2) , korrekt?


int resultat = 0;

for(int i = 0; i<=n ;i+=2 )
{
resultat = resultat+i;
}

#7 - arne_v
19. mar. 2009 00:27

#4

Det er halvsvært at lave en for løkke uden jump !

#8 - arne_v
19. mar. 2009 00:28

#5

En løkke med n gennemløb er O(n) sålænge der ikke er noget inde i løkken der varierer med n.

#9 - arne_v
19. mar. 2009 00:30

#6

Nej. Den er stadig O(n).

O(n) betyder at T(n) konvergerer mod a*n hvor a er en konstant når n går mod uendelig.

#10 - arne_v
19. mar. 2009 00:31

Man skelner kun mellem:

O(1)
O(n)
O(logn)
O(nlogn)
O(n^2)
O(n^3)
O(2^n)
o.s.v.

#11 - arne_v
19. mar. 2009 00:33

Af respekt så burde man formentlig bruge MIX instruktioner til at analysere den præcise kompleksitet.

#12 - Windcape
19. mar. 2009 00:34

Så tror jeg at jeg er ved at have lidt bedre styr på det :-)

Mange tak.

#13 - arne_v
19. mar. 2009 00:38

http://en.wikipedia.org/wiki/Big_O_notation

har lidt mere matematik.

#14 - arne_v
19. mar. 2009 00:38

Og Knuth er obligatorisk læsning for den slags !

#15 - Windcape
19. mar. 2009 01:13

Lige een mere:


int T(int n)
{
int result = 0;
for (int i = 0; i < n; i++)
{
for (int j = 1; j < n; j = j*2)
{
result++;
}
}
return result;
}

Det ydre loop itereres over N gange, og den indre løkke itereres over N ∙ M, men da det er meget variabel må tidskompleksiteten kunne tilnærmes til O(n).

Har jeg forstået det rigtigt?

#16 - arne_v
19. mar. 2009 02:19

#15

Den ydre løkke gennemløbes n gange.

Den indre løkke gennemløbes log2(n) gange.

Kompleksiteten må derfor være O(nlog(n)).

#17 - arne_v
19. mar. 2009 02:21

#16

Tror jeg ihvertfald.

Det er 20 år siden jeg var til eksamen i den slags.

#18 - arne_v
19. mar. 2009 02:22

#16

Da loga(n)=log(n) /log(a) så skelner man ikke mellem hvilken logaritme det er.

#19 - Windcape
19. mar. 2009 02:22

Det er godt nok kun 4 år siden her, men jeg kan dårlig nok huske noget.

Må hellere få læst op på logaritmer.

Tak igen.

#20 - arne_v
19. mar. 2009 02:24

#19

Det er 20 år siden jeg var til eksamen i big O.

Logaritmer er lidt flere år siden.

#21 - Windcape
19. mar. 2009 02:39

hehe :)

Jeg checkede også, det er Log2 som benyttes. Umidbart må det kræve noget erfaring at kunne se igennem at det er base2 der benyttes.

#22 - arne_v
19. mar. 2009 13:07

#21

j = j*2 => base 2
j = j*10 => base 10

#23 - arne_v
19. mar. 2009 17:42

Udover at analysere sig frem kan man også teste.

For fun:

public class BigOTester {
public interface Algorithm {
public int t(int n);
}
private static long time(Algorithm alg, int n, int rep) {
long t1 = System.currentTimeMillis();
for(int i = 0; i < rep; i++) {
alg.t(n);
}
long t2 = System.currentTimeMillis();
return t2 - t1;
}
private final static int SECS = 5;
private static double time(Algorithm alg, int n) {
int repprsec = 1;
while(time(alg, n, repprsec) < 1000) repprsec *= 2;
int rep = SECS * repprsec;
return time(alg, n, rep) / (double)rep;
}
private final static double MAXDEV = 0.05;
private final static boolean match(double tlow, double thigh, double clow, double chigh) {
double ratio = (thigh / tlow) / (chigh / clow);
return (1 - MAXDEV) < ratio && (ratio < 1 + MAXDEV);
}
private final static int LOW = 1000;
private final static int HIGH = 10000;
public static void test(Algorithm alg) {
double tlow = time(alg, LOW);
double thigh = time(alg, HIGH);
if(match(tlow, thigh, 1.0, 1.0)) {
System.out.println("O(1)");
} else if(match(tlow, thigh, Math.log(LOW), Math.log(HIGH))) {
System.out.println("O(logn)");
} else if(match(tlow, thigh, (double)LOW, (double)HIGH)) {
System.out.println("O(n)");
} else if(match(tlow, thigh, (double)LOW * Math.log(LOW), (double)HIGH * Math.log(HIGH))) {
System.out.println("O(nlogn)");
} else if(match(tlow, thigh, (double)LOW * (double)LOW, (double)HIGH * (double)HIGH)) {
System.out.println("O(n^2)");
} else if(match(tlow, thigh, Math.pow(LOW, 3), Math.pow(HIGH, 3))) {
System.out.println("O(n^3)");
} else {
System.out.println("Unknown big O");
}
}
public static void main(String[] args) {
test(new Algorithm() {
public int t(int n) {
int result = 0;
for(int i = 0; i < n ; i++)
{
result = result + i;
}
return result;
}
});
test(new Algorithm() {
public int t(int n) {
int result = 0;
for(int i = 0; i < n ; i += 2)
{
result = result + i;
}
return result;
}
});
test(new Algorithm() {
public int t(int n)
{
int result = 0;
for (int i = 0; i < n; i++)
{
for (int j = 1; j < n; j *= 2)
{
result++;
}
}
return result;
}
});
}
}

mboost-dp1

Nyheder

Seneste kommentarer i nyheder

Seneste kommentarer i forum

Algoritm Tids Kompliexitet - Java