Zeitkomlpexität,Speicherkomplexität

Neue Frage »

Auf diesen Beitrag antworten »
matheFranzi1991 Zeitkomlpexität,Speicherkomplexität

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.
 
Auf diesen Beitrag antworten »
3FingerbreitNougat

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
 
Neue Frage »
Antworten »


Verwandte Themen