Welchen Aufwand O haben die Methoden algorithmus1() bis algorithmus8() des folgenden Programms abhängig vom Übergabeparameter n?
Gehen Sie davon aus, das der Java JIT (Just in Time Compiler) nichts optimiert.
Hinweis: Wie oft werden die jeweiligen Schleifen durchlaufen? Welche Durchläufe sind konstant, welche variabel?
package Kurs2.Sort;public class Komplexität {
private static int groesse = 1000;
public static void main(String[] args) {
algorithmus1(groesse);
algorithmus2(groesse);
algorithmus3(groesse);
algorithmus4(groesse);
algorithmus5(groesse);
algorithmus6(groesse);
algorithmus7(groesse);
}public static void algorithmus1(int n) {
for (int i = 1; i < n; i++) {
int k = i * 2;
}
}public static void algorithmus2(int n) {
for (int i = 1; i < n; i++) {
for (int j = 1; j < 1000; j++) {
int k = j - i;
}
}
}public static void algorithmus3(int n) {
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
int k = j - i;
}
}
}public static void algorithmus4(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;
}
}
}
}public static void algorithmus5(int n) {
for (int i = 1; i < n; i++) {
for (int j = 1; j < 1000; i++) {
int k = j - i;
}
for (int j = 1; j < 1000; j++) {
int k = j - i;
}
}
}public static void algorithmus6(int n) {
for (int i = 1; i < n; i++) {
for (int j = 1; j < i; j++) {
int k = j - i;
}
}
}public static void algorithmus7(int n) {
for (int i = 1; i < 1000; i++) {
int j = 0;
while (j < 1000) {
j++;
int k = 2 * j;
}
}
}
public static void algorithmus8(int n) {
for (int i = 1; i < n; i++) {
algorithmus1(n);
}
}
} // Ende der Klasse
Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).
Niveau | 2 |
Schwierigkeitsgrad | mittel |
Zeit | 16 Minuten |
Antwort zu Frage 7:Komplexitätsbetrachtungen 2
Nr. | Quellcode | Antwort |
---|---|---|
public class K1 { |
Nichts in dieses Feld eintragen! | |
Bsp. |
static void algorithmusBsp(int n) { |
Beispiel: Ofor1(n)+Ofor2(n) = O(n) |
1. |
static void algorithmus1(int n) { |
Ofor1(n)+Ofor2(1000)= Ofor1(n)+Ofor2(1) = O(n) |
2. |
static void algorithmus2(int n) { |
Ofor1(n)*Ofor2(n)*Ofor3(n) = O(n3) |
3. |
static void algorithmus3(int n) { |
Ofor1(n)*Ofor2(n)*(Owhile1(n)+Owhile2(n)) Ofor1(n)*Ofor2(n)*2*Owhile(n)= 2*O(n3) = O(n3) |
4. |
static void algorithmus4(int n) { |
Ofor(n)*Ofor2(1000)*Oalgorithmus2(n3) = O(n4) |
}// Ende der Klasse |
--- |
- Printer-friendly version
- Log in to post comments
- 4086 views
Aufgabe fragt nur für A1-7
In der Aufgabenstellung wird nur nach den Algorithmen 1-7 gefragt, in der Lösung sind alle vorhanden.
Stimmt
Danke. Wurde verbessert.