6 Komplexitätsbetrachtungen 1
6 Komplexitätsbetrachtungen 1Welche Komplexität haben die gezeigten Javamethoden?
Gegeben ist das folgende Javaprogramm:
Nr. | Quellcode | Antwort |
---|---|---|
public class K1 { |
nichts eintragen | |
Bsp. |
static void algorithmusBsp(int n) { for (int i = 1; i < n; i++) { int k = i * 2; } for (int j = 1; j < n; j++) { int k = j * 3; } } |
Beispiel: Ofor1(n)+Ofor2(n) = O(n) |
1. |
static void algorithmus1(int n) { for (int i = 1; i < n; i++) { int k = i * 2; } for (int i = 1; i < 1000; i++) { int k = i +2; } } |
|
2. |
static void algorithmus2(int n) { for (int i = 1; i < n; i++) { int p = n; for (int j = 1; j < p; j++) { int k = j - i; } } } |
|
3. |
static void algorithmus3(int n) { for (int i = 1; i < n; i++) { for (int j = 1; j < n; j++) { for (int k = 1; k < n; k++) { int q = k - j - i; } int p=0; while (p<n) { p++; int r = n*p; } } } } |
|
4. |
static void algorithmus4(int n) { for (int i = 1; i < n; i++) { for (int j = 1; j < 1000; j++) { algorithmus2(n); } } } |
|
}// Ende der Klasse |
Nichts eintragen |
Die Antwort finden Sie auf der nächsten Seite (URL rechts unten klicken).
Niveau | 2 |
Schwierigkeitsgrad | mittel |
Zeit | 8 Minuten |
Antwort zu Frage 5: Erklärung der Heapbedingung
Das Feld soll aufsteigend sortiert werden.
Jeder Vaterknoten muss größer als beide Unterknoten sein oder auch: jeder Knoten mit dem Index i muss größer als existierende Knoten mit Index 2*i und 2*i+1 sein.
- 4636 views
Antwort zu Frage 5
M.E. sind die Aussagen "Jeder Vaterknoten muss größer als beide Unterknoten sein." und "Jeder Knoten mit dem Index i muss größer als existierende Knoten mit Index 2*i und 2*i+1 sein." redundant. Könnten sie das bitte in der Antwort ersichtlich machen?
OK, richtig
Erledigt.