理解具有嵌套循環的函數的理論運行時間

Question

我一直在試圖理解Big-O符號。今天早些時候，我被賦予了練習的功能，並告知它有一個O(n^5)。我嘗試過自己計算，但不知道我是否正確計算了T(n)。

這裏是我的兩個問題：

1）我有沒有計算T(n)正確，如果沒有的話我做了什麼錯？

2）爲什麼我們只關心變量的最高功率？

1 sum = 0;       //1     = 1 
2 for(i=0; i < n; i++)   //1 + n + 2(n-1) = 1+n+2n-2   = 3n-1 
3  for (j=0; j < i*i; j++)   //n + n*n + 2n(n-1))= n+ n^2 + 2n^2-2n = 3n^2 -n 
4  for (k=0; k < j; k++)   //n + n*n + 4n(n-1))= n + n*n +4n*n-4n = 5n^2 -3n 
5   sum++; 
6   k++; 
7  j++; 
8 i++; 
// so now that I have simplified everything I multiplied the equations on lines 2-4 and added line 1 
// T(n) = 1 + (3n-1)(3n^2-n)(5n^2 -3n) = 45n^5 -57n^4 +23n^3 -3n^2 + 1 

Answer 1

最內圈循環運行j次。 第二個循環運行j = 0 to i^2 - >整數之和。 外循環運行到n - >平方和和4次冪整數。

我們只取最高權力因爲n趨於無窮大的n（或訂單）的最高功率將始終佔據主導地位，不論其係數。