Wenn wir die Summe von n Zahlen mit For-Schleife machen ** ex.for (i = 1; i <= n; i ++) **

Question

wenn wir die Summe n Zahlen mit for-Schleife for(i=1;i<=n;i++) Komplexität davon ist O (n), aber wenn wir diese gleiche Berechnung unter Verwendung der Formel der arithmetischen/geometrischen Progression Serie n(n-1)/2 dieser Zeit, wenn wir die Zeit Komplexität berechnen, ist es O (n^2). Wie ? Bitte löse meine Zweifel.

Answer 1

Ihre zweite Formel hat O(1) Komplexität, das heißt, es läuft in konstanter Zeit, unabhängig von n.

Es gibt keinen Widerspruch. Die Komplexität ist ein Maß dafür, wie lange der Algorithmus zum Ausführen benötigt. Verschiedene Algorithmen können dasselbe Ergebnis mit unterschiedlichen Geschwindigkeiten berechnen.

[BTW die richtige Formel ist n*(n+1)/2.]

Edit: Vielleicht ist Ihre Verwirrung mit einem Algorithmus zu tun hat, die n*(n+1)/2 Schritte unternimmt, die (n^2 + n)/2 Schritte ist. Wir nennen das O(n^2), weil es im Wesentlichen (asymptotisch) wie n^2 wächst, wenn n groß wird. Das heißt, es wächst in der Größenordnung vonn^2, der Term hoher Ordnung des Polynoms.

Answer 2

Sie sind verwirrt, was die Zahlen darstellen.

Grundsätzlich zählen wir die # Schritte, wenn wir über Komplexität sprechen.

n(n+1)/2 die Antwort der Summation ist (1..n), das ist richtig, aber unterschiedliche Art und Weise anders # nehmen von es zu berechnen, die Schritte, und wir werden die # solcher Schritte zu zählen.

Vergleichen Sie die folgenden:

int ans = 0; 
for(int i=1; i<=n;i++) ans += i; 
// this use n steps only 

int ans2 = 0; 
ans2 = n*(n+1)/2; 
// this use 1 step!! 

int ans3 = 0; 
for(int i=1, mx = n*(n+1)/2; i<=mx; i++) ans3++; 
// this takes n*(n+1)/2 step 
// You were thinking the formula would look like this when translated into code! 

Alle drei Antworten den gleichen Wert geben!

So können Sie nur die erste Methode siehe & die dritte Methode (was natürlich überhaupt nicht praktisch) von n, unterschiedliche n betroffen ist, wird sie nehmen unterschiedliche Schritte führen, während das zweite Verfahren, das die Formel verwendet, nehmen immer 1 Schritt, egal was n

Being sagte ist, wenn Sie die Formel im Voraus wissen, es ist immer das beste, was Sie berechnen nur die Antwort direkt mit der Formel