Ich weiß, dass dies keine reine Programmierfrage ist, aber es ist eineist Ich hoffe, jemand kann mir helfen.

Ich habe an meinen Algorithmus-Hausaufgaben gearbeitet und das Big-Oh, Big-Omega, Theta usw. mehrerer Algorithmen herausgefunden. Ich beweise sie, indem ich ihr C und N finde0 Werte und alles läuft gut.

Ich bin jedoch auf meine letzten beiden Probleme im Set gestoßen und habe Mühe, herauszufinden, wie ich sie lösen soll (und Google hilft nicht viel).

Ich musste noch nie das Big-Oh / Omega der Summen herausfinden.

Meine letzten beiden Probleme sind:

Zeige, dassΣ (i = 1 bis n) von i2 ist O (N3)

und

Zeige, dassΣ (i = 1 bis n) von [log2ich] ist Ω (n log n)

Meine Frage ist: Wie zeige ich das?

Zum Beispiel kann ich in der ersten intuitiv nicht sehen, wie diese Summe von i2 ist O (N3). Der zweite verwirrt mich noch mehr. Kann jemand erklären, wie man das Big-Oh und das Big-Omega dieser Summierungen zeigt?