Summenfolge (n^2-1^2) + 2(n^2-2^2) +….n(n^2-n^2)

In diesem Artikel werden wir uns verschiedene Möglichkeiten ansehen, die Summe einer Folge zu berechnen – (n^2 – 1^2) + 2(n^2 – 2^2) + n(n^2 –). n^2 ). Bei der ersten Methode berechnen wir nacheinander die Sequenzsumme für jedes i im Bereich 1 bis n und addieren sie zur Endsumme.

Bei der zweiten Methode leiten wir eine mathematische Formel ab, um die Summe einer bestimmten Reihe zu berechnen, wodurch die zeitliche Komplexität des Programms von O(n) auf O(1) reduziert wird.

Problemstellung − Wir erhalten eine Zahl „n“ und unsere Aufgabe besteht darin, die Summe der gegebenen Folge (n^2 - 1^2) + 2(n^2 - 2^2) + … zu berechnen ( n^2 - n^2).

Beispiel

Eingabe − Zahl = 5

Ausgabe – Wenn n = 5, beträgt die Summe der Reihe (n^2 – 1^2) + 2(n^2 – 2^2) + … .

Eingabe − Zahl = 3

Ausgabe – Für n = 3 beträgt die Summe der Reihe (n^2 – 1^2) + 2(n^2 – 2^2) + ….n(n^2 – n^2) 18 .

Methode 1

Dies ist die einfachste Brute-Force-Methode zur Lösung des Sequenzsummenproblems.

Nach sorgfältiger Analyse dieser Folge können wir schlussfolgern: Für jede Zahl n gilt

Summe = ∑ i*(n^2 - i^2) für i = 1 bis i = n.

Für die Brute-Force-Methode können wir also die obige Formel in einer Schleife mit i von 1 bis n verwenden, um die erforderliche Summierung zu erzeugen.

Beispiel

Der Code für diese Methode lautet wie folgt:

#include <bits/stdc++.h>
using namespace std;
int main () {
   int num = 3;
   long long sum=0;
   for (int i=1  ; i<num ; i++ ) {
      sum = sum+i*( num*num - i*i );
   }
   cout<< " The sum of the series (n^2 - 1^2) + 2(n^2 - 2^2) + …. n(n^2 - n^2) for n = " << num << " is " <<sum;
   return 0;
}

Ausgabe

The sum of the series (n^2 - 1^2) + 2(n^2 - 2^2) + …. n(n^2 - n^2) for n = 3 is 18

Komplexität

Zeitkomplexität – O(n), während wir die Schleife von 1 bis n durchlaufen.

Raumkomplexität – Da wir keinen externen Raum verwenden, beträgt die Raumkomplexität dieser Methode O(1).

Methode 2

In dieser Methode leiten wir eine Formel ab, die direkt die erforderliche Sequenzsumme erhält, sodass keine Iteration erforderlich ist. Diese Methode löst das gegebene Problem mit konstanter Zeitkomplexität.

Wie bereits erwähnt, erhalten wir die allgemeine Version der Serie, angegeben als

Sum = ∑ i*(n^2 - i^2) for i = 1 to i = n.

Die gleiche Serie kann geschrieben werden als:

Sum =  n^2∑ i - ∑ i^3

Wir kennen bereits die Formeln zur Berechnung der Summe aller Zahlen von 1 bis n bzw. die Formel zur Berechnung der Kubiksumme aller Zahlen von 1 bis n:

Die Summe aller Zahlen von 1 bis n

n* ( n+1 )/2 

Wobei n die angegebene Zahl ist.

Ermitteln Sie nun die Würfelsumme aller Zahlen von 1 bis n

(n*( n+1 )/2)^2

Die gegebene Serie kann also geschrieben werden als-

Sum = n^2 * ( n*( n+1 )/2 ) – ( n*( n+1 )/2 )^2

Summe kann weiter vereinfacht werden zu -

Sum = ( n * (n+1)/2 )*( n^2 - ( n * (n+1)/2 ))
Sum = n^2 * ( n+1 )/2 * ( n^2 – (n * ( n+1))/2)
Sum = n^2 * ( n+1 ) * ( n-1 )/4
Sum = n^2 * ( n^2 -1 )/4
Sum = (n^4)/4 – (n^2)/4

Wir müssen also nur Sum = (n^4)/4 - (n^2)/4 für jedes n berechnen, um die Summe der gewünschten Sequenzen zu erhalten.

Beispiel

Der Code für diese Methode lautet wie folgt:

#include <bits/stdc++.h>
using namespace std;
int main () {
   int num = 5;
   long long sum = 0;
   sum = num*num*(num*num-1)/4;
   cout<< " The sum of the series (n^2-1^2) + 2(n^2-2^2) + …. n(n^2-n^2) for n = " << num << " is " <<sum;
   return 0;
}

Ausgabe

The sum of the series (n^2-1^2) + 2(n^2-2^2) + …. n(n^2-n^2) for n = 5 is 150

Komplexität

Zeitkomplexität – O(1), da wir lediglich die erforderliche Summe anhand der von uns abgeleiteten Formel berechnen.

Raumkomplexität – Da wir keinen externen Raum verwenden, beträgt die Raumkomplexität dieser Methode O(1).

Fazit – In diesem Artikel haben wir zwei Methoden zur Berechnung der erforderlichen Summe einer Reihe besprochen und mit der zweiten Methode haben wir die Zeitkomplexität auf eine Konstante reduziert.

Das obige ist der detaillierte Inhalt vonSummenfolge (n^2-1^2) + 2(n^2-2^2) +….n(n^2-n^2). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!