Zeit Komplexität der Funktion eine andere Funktion aufrufen?

Ich weiß, wie die Zeit Komplexität für fast jede Option zu finden (einfache Funktion, Funktion mit Schleifen, etc.), aber ich kann nicht herausfinden, wie Zeit Komplexität der Funktion, die eine andere Funktion zu bestimmen, insbesondere wenn Die aufrufende Funktion befindet sich in einer Schleife.Zeit Komplexität der Funktion eine andere Funktion aufrufen?

Ich schrieb einige Funktionen, die ich als Beispiel verwende.

int g(int k) { 
    int i=0; 

    while(k>0) { 
    i += k; 
    k= k/2; 
    } 

    return i; 
} 

int f(int n) { 
    int m = 0; 

    for (int i=0; i<n; ++i) { 
    for (int j=i; j<n; ++j) { 
     m += g(j); 
    } 
    } 

    return m; 
}

ich kann nicht herausfinden: habe ich die Zeit Komplexität der Funktion g(), zu prüfen, und wenn es sein muss, wie es f() in Funktion berechnen? Oder ignoriere ich einfach die Funktion g() und schließe nur die Funktionsaufrufe in die Funktion f() ein?

Quelle

2016-06-30 DataJayden

Da die Komplexität der Funktion g vom Parameter k (logarithmisch) abhängt, müssen Sie sie beim Aufruf von Funktion f berücksichtigen. Falls die Worst-Case-Operation von g konstante Zeitkomplexität aufweist, müssen Sie sie möglicherweise nicht explizit berücksichtigen.

In Ihrem Fall f die Komplexität O (n) & Komplexität G ist O (lg (n)), eine Gesamtkomplexität von O Nachgeben (n LG (n))

Quelle

2016-06-30 21:22:57

complexitiy der f O (n^2 ln (n)), es würde sei O (n^2) wenn g eine konstante Komplexität hätte – user463035818

Vereinbare mit tobi303, wenn die Funktion g eine konstante Komplexität hätte, dann wäre die Gesamtkomplexität O (n^2). –

Warum schreiben Sie dann "fs Komplexität ist O (n^2)"? Das ist irreführend. – user463035818

Sie müssen die Komplexität von g in f berücksichtigen.

g hat O(log(n)) Komplexität.

so ist die Komplexität von f die Summe dieser Komplexität log(j) s.

Im schlimmsten Fall ist es O(n²log(n)).

Quelle

2016-06-30 21:14:11 Jarod42

Um die Komplexität von f zu finden, kapseln Sie einfach den Code von g innerhalb von f und denken Sie, als ob dies eine einzelne ganze Funktion wäre. Der Aufruf selbst ist O (1) und hat somit keinen Einfluss auf die Komplexität, als ob der Code in g an der Stelle ausgeführt würde, an der g aufgerufen wird.

Dies wäre in einigen Fällen unwahr, wenn Sie beispielsweise ein Array der Größe n als Parameter an die Funktion übergeben: In diesem Fall wäre die Array-Kopie selbst O (n), also würde der Aufruf erfolgen Auswirkungen auf die Komplexität haben.

Quelle

2016-06-30 21:45:01 galinette

Dies wird n²log intuitiv (n), aber genauer gesagt, erhalten Sie folgenden Beweis: