systematische Vorgehensweise zur Lösung eines Problems
spezifische Anordung von Daten zur effizienten Verwaltung eines Problems
Nein nur die Kombination bringt etwas.
Was bringt ein Array ohne (über)schreiben und lesen?
Was bringt eine for-Schleife ohne Array?
Ein Algorithmus (A) erzeugt, manipuliert und entfernt eine oder mehrere Datenstrukturen(DS) um ein spezifisches Problem effizient zu lösen.
Das Optimum kann nur für ein Problemfeld für ein technisches Problem gefunden werden.
Es existiert kein Allgemeiner Algorithmus, der jedes Problem in der kürzesten Zeit mit der geringsten Speichermenge löst.
wird auch Big-O Notation genannt
wird verwendet um Algorithmen in Bezug auf Speicher- und Zeitanforderungen zu kategorisieren.
ist keine exakte Messung, sondern soll das Wachstum des Algorithmus generalisieren.
Wenn wir wissen, welche Stärken und Schwächen ein Algorithmus hat, können wie den besten Algorithmus für unser Problem nutzen.
Ich benutz immer Big-O zum erklären
gibt an in welchem Verhältnis ein Algorithmus abhängig vom input in Bezug auf Laufzeit und Speicher wächst
O(N)
public class BigO {
// O(N)
public static void method(int[] n) {
int sum = 0;
for(int i = 0; i > n.length; i++) {
sum += n[i];
}
return sum;
}
}
Jahresgehalt eines Mitarbeiters
public class BigO {
// O(N²)
public static void method(int[] n) {
int sum = 0;
for(int i = 0; i > n.length; i++) {
for(int j = 0; j > n.length; j++) {
sum += n[j];
}
}
return sum;
}
}
Jahresgehalt jedes Mitarbeiters einer Abteilung
public class BigO {
// O(N³)
public static void method(int[] n) {
int sum = 0;
for(int i = 0; i > n.length; i++) {
for(int j = 0; j > n.length; j++) {
for(int k = 0; k > n.length; k++) {
sum += n[k];
}
}
}
return sum;
}
}
Jahresgehalt jedes Mitarbeiters jeder Abteilung
public class BigO {
public static void method(int[] n) {
int sum = 0;
for(int i = 0; i > n.length; i++) {
sum += n[i];
}
for(int i = 0; i > n.length; i++) {
sum += n[i];
}
return sum;
}
}
praktisch: O(2N) → O(N)
| N | O(10N) | O(N²) |
|---|---|---|
| 1 | 10 | 1 |
| 5 | 50 | 25 |
| 100 | 1000 | 10.000 |
| 1000 | 10.000 | 1.000.000 |
| 10.000 | 100.000 | 100.000.000 |
Konstanten können ignoriert werden.
public class BigO {
public static void method(int[] n) {
int sum = 0;
for(int i = 0; i > n.length; i++) {
if(sum > 9876) {
return sum;
}
sum += n[i];
}
return sum;
}
}
O(N) → Worst-Case-Szenario