2016-06-11 4 views
1

Ich bin neu in Algorithmen und sehr daran interessiert, sie zu lernen und zu implementieren.
Lernen Sie sie durch alle verfügbaren Online-Materialien, die ich finden kann. Ich bin ein wenig verwirrt in Bezug auf diese -Was ist die Komplexität, wenn eine Schleife zweimal vom selben Eingangsarray ausgeführt wird?

Betrachten Sie diesen Code -

for (int i=0; i<n; i++) { ..... } 
for (int i=0; i<n; i++) { ..... } 

Was die Komplexität wird dies sein?
O (n) oder O (n^2)?

+0

die Laufzeit der ersten Schleife Angenommen, war 'n = 5' Einheiten. Wie hoch ist die Gesamtlaufzeit, 10 Einheiten ('2 * n') oder 25 Einheiten (' n^2')? –

+0

Im Allgemeinen habe ich es immer als verschachtelte Schleifen betrachtet, die du multiplizierst und aufeinanderfolgende Schleifen hinzufügst. Konstanten fallen aus der letzten Komplexität –

+0

'O (n * schlechteste_Runtime_of_both {......})' – lllllllllll

Antwort

2

Angenommen, die { . . . } ist konstante Zeit, dann ist die Komplexität einer Schleife O (n).

Was ist die Komplexität von zwei "benachbarten" Schleifen? Es ist O (n) + O (n). Oder man könnte sich das als O (n + n) -> O (2n) vorstellen. Konstanten fallen aus der Komplexität heraus, also ist dies O (n).

Es ist eine völlig andere Sache mit verschachtelten Schleifen. Also folgendes:

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

wäre O (n^2).

1

Die Komplexität wird O (n)

(Unter der Annahme, dass Sie für Schleifen nicht innerhalb diejenigen haben eine andere Schleife) bleiben.

1

Die Idee hinter der Berechnung der Zeit Komplexität ist, wie viel Zeit Ihre Schleife/Funktion führt jeden Schritt darin aus?
zum Beispiel: for Schleife

for (int i=0; i < n; i++) { 
    cout << "hello" << endl; 
} 

der Code in geschweiften Klammern werden n mal hello so die Zeitkomplexität dieser for-Schleife wird O(n)

for (int i=0; i < n; i++) { 
    cout << "hello" << endl; 
} 
for (int i=0; i < n; i++) { 
    cout << "hello" << endl; 
} 

dies mehr gedruckt werden hello 2 Zeit drucken als das vorherige, da es zwei for-Schleife hat. Zeitkomplexität ist O (2n). Wir ignorieren die Konstanten, während die Zeit Komplexität der Berechnung so die Komplexität der Zeit sein wird, O(n)

for (int i=0; i < n; i++) { 
    for (int j=0; j < n; j++) { 
     cout << "hello" << endl; 
    } 
} 

diese hellon^2 Zeit gedruckt werden, warum? denn für jede äußere for loop (i) führen Sie innere for loop(j)O(n) Zeit. so wird O(n^2) Zeitkomplexität sein

weiter lesen http://www.geeksforgeeks.org/analysis-of-algorithms-set-4-analysis-of-loops/

Verwandte Themen