Hierbei handelt es sich um die Original-Variante.
Variante | 1.a (iterativ) |
Typ | standard |
Eigenschaften | iterativ, nicht parallelisierbar |
Datenstrukturen | Felder, einfachverkettete Listen |
Speicher | Ω(1) | Θ(1) | Ο(1) |
Laufzeit | Ω(1) | Θ(n) | Ο(n) |
Vergleiche (found) | 1 | n/2 | n |
Vergleiche (not found) | n | n | n |
int fmsearch(field A, int l, int r, element ele) {
for i:=l to r do {
if (A[i] = ele) then {
return i;
}
}
return -1;
}
| |
Variante | 1.b (rekursiv) |
Typ | standard |
Eigenschaften | rekursiv, nicht parallelisierbar |
Datenstrukturen | Felder, einfachverkettete Listen |
Speicher | Ω(1) | Θ(n) | Ο(n) |
Laufzeit | Ω(1) | Θ(n) | Ο(n) |
Vergleiche (found) | 1 | n/2 | n |
Vergleiche (not found) | n | n | n |
int fmsearch(field A, int l, int r, element ele) {
if (l > r) then {
return -1;
} else if (A[l] = ele) then {
return l;
} else {
fmsearch(A,l+1,r,ele);
}
}
| |
|