6 Komplexitätsbetrachtungen 1

6 Komplexitätsbetrachtungen 1

Welche Komplexität haben die gezeigten Javamethoden?

Gegeben ist das folgende Javaprogramm:

Nr. Quellcode Antwort
 
public class K1 {

private static int groesse = 1000;

public static void main(String[] args) {
algorithmusBsp(groesse);
algorithmus1(groesse);
algorithmus2(groesse);
algorithmus3(groesse);
algorithmus4(groesse);
}

 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.

javafrage Mon, 02/13/2012 - 09:42

Anonymous (not verified)

Tue, 06/27/2017 - 11:32

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?