Tricky Big-O Komplexität

Question

public void foo(int n, int m) { 
    int i = m; 

    while (i > 100) { 
     i = i/3; 
    } 
    for (int k = i ; k >= 0; k--) { 
     for (int j = 1; j < n; j *= 2) { 
      System.out.print(k + "\t" + j); 
     } 
     System.out.println(); 
    } 
} 

Ich dachte, die Komplexität wäre O (logn).
Das ist als ein Produkt der inneren Schleife, die äußere Schleife - wird nie mehr als 100 mal ausgeführt werden, so dass es weggelassen werden kann.

Worüber ich nicht sicher bin, ist die while-Klausel, sollte sie in die Big-O-Komplexität integriert werden? Für sehr große i Werte könnte es eine Auswirkung haben, oder arithmetische Operationen, spielt keine Rolle in welcher Größenordnung, zählen als Grundoperationen und kann weggelassen werden?

Answer 1

Die while Schleife ist O(log m) weil Sie m durch 3 Dividieren halten, bis sie unter oder gleich 100 ist.

Da 100 in Ihrem Fall eine Konstante ist, kann es ignoriert werden, ja.

Die innere Schleife ist O(log n) wie Sie sagten, weil Sie multiplizieren j von , bis es n überschreitet.

Daher ist die Gesamtkomplexität O(log n + log m).

oder arithmetische Operationen, spielt keine Rolle in welcher Größenordnung, zählen als Grundoperationen und können weggelassen werden?

Arithmetische Operationen können normalerweise weggelassen werden, ja. Es hängt aber auch von der Sprache ab. Dies sieht wie Java aus und es sieht so aus, als ob Sie primitive Typen verwenden. In diesem Fall ist es in Ordnung, arithmetische Operationen zu betrachten O(1), ja. Aber wenn Sie beispielsweise große Ganzzahlen verwenden, ist das nicht mehr ganz ok, da Addition und Multiplikation nicht mehr O(1) sind.

Answer 2

Die Komplexität ist O (log m + log n).

Die While-Schleife führt log3 (m) mal aus - eine Konstante (log3 (100)). Die äußere for-Schleife wird eine konstante Anzahl von Malen ausgeführt (etwa 100), und die innere Schleife führt log2 (n) -mal aus.

Answer 3

Die while-Schleife den Wert von m um einen Faktor von 3 teilt, damit die Anzahl solcher Operationen lügen werden (Basis 3) m

der Für-Schleifen man von der Anzahl der Operationen, wie 2 einfiel Summierungen -

Summierung (k = 0 bis i) [Summation (j = 0 bis lg n) (1)] Summierung (k = 0 bis i) [lg n + 1] (lg n + 1) (i + 1) wird die Gesamtanzahl von Operationen sein, von denen der Log-Term dominiert.

Deshalb ist die Komplexität es Hausaufgaben für Tagging und ehrlich 2