Eksempler
Vi skal her ta for oss to ulike algoritmer, Alg1 og Alg2 (BigOh.java). Vi skal studere i detalj hvordan tidsbruken til algoritmene henger sammen med størrelsen på input, her (og som regel) uttrykt ved variabelen N. Først vil vi se på sammenhengen mellom kjøretidene for de to metodene for ulike intervaller av input størrelse. Deretter ser vi i detalj på Alg1 og Alg2.
Erfaringene fra disse eksemplene brukes så til å formulere to generelle metoder for å finne en algoritmes orden.
Alg1
Den første algoritmen kaller to metoder, A1 og B1:
public void Alg1(int[] arr, int j) {
int new_arr[] = B1(arr.length+1);
for (int i = 0; i < arr.length; i++ ) {
A1(new_arr, arr, i);
}
new_arr[arr.length] = j;
}
private void A1(int[] a1, int[] a2, int j) {
int max = 100000;
for (int i = 0; i < max; i++) {
a1[j] = a2[j];
}
}
private int[] B1(int k) {
int max = 100000;
int[] arr = null;
for (int i = 0; i < max; i++) {
arr = new int[k];
}
return arr;
}
Alg2
Også den andre algoritmen inneholder to metoder, A2 og B2:
public void Alg2(int j) {
int k = B2(j);
int l = 3;
while (k > 0) {
k = A2(k, l);
}
}
private int B2(int j) {
int max = 100000000;
int k = 0;
for (int i = 0; i < max; i++) {
k = j;
}
return k;
}
private int A2(int j, int l) {
int max = 1000000;
int k = 0;
for (int i = 0; i < max; i++) {
k = j/l;
}
return k;
}