Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Zeitkomlpexität,Speicherkomplexität » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen Zeitkomlpexität,Speicherkomplexität
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
matheFranzi1991
Grünschnabel


Dabei seit: 02.11.2010
Beiträge: 1

Zeitkomlpexität,Speicherkomplexität Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Meine Frage:
Folgendes ist gegeben

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
int function ( int n ) {
  int sum = 0;

  for(int i=1; i<=n; i=2*i) {
    for(int j=n; j>0; j--) {
      for(int k=0; k<2*n; k++) {
        sum = sum + i*(j+k); 
      }
    }
  }
 
  return sum;
}


gesucht: obere schranke, Zeitkomplexität,Speicherkomplexität

Meine Ideen:
Würde sagen weil hier das Wachstum linerar ist muss die O-Notation O(logn) sein oder sowas, hab echt keine ahnugn bitte helft mir.
02.11.2010 14:54 matheFranzi1991 ist offline E-Mail an matheFranzi1991 senden Beiträge von matheFranzi1991 suchen Nehmen Sie matheFranzi1991 in Ihre Freundesliste auf
3FingerbreitNougat
unregistriert
Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Also Zeitkomplexität in O-Notation:

Erstes for: wird log(n) mal durchlaufen.
Zweites for wird log(n) * n mal durchlaufen.
Drittes for wird log(n) * n * 2n mal durchlaufen.

Die Obere Schranke ist ne dreifache Summenformel, zu der ich aber gerade keine Zeit hab weil ich gleich Uni muss. Werde später nochmal reinschauen.

MfG
02.11.2010 16:08
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Zeitkomlpexität,Speicherkomplexität