下面的代碼片段O（n^2）的時間複雜度是多少？

Question

我在想，如果下面的代碼片段的時間複雜度爲O(n^2)：

class Solution { 
public: 

    int numSquares(int n) { 
     if(n<=0) 
      return 0; 

     vector<int> dp(n+1, INT_MAX); 
     dp[0]=0; 
     for(int i=1; i<=n; i++) { 
      for(int j=1; j*j<=i; j++) { 
       //+1 because you are adding the current `j` 
       dp[i]=min(dp[i], dp[i-j*j]+1); 
      } 
     } 

     return dp[n]; 
    } 
}; 

我不知道，因爲在內部循環，我們正在檢查完全平方不到i，這將是非常少與i比較（我認爲這麼少，他們可以被認爲是不變的）。在這種情況下，複雜性只會是O(n)。那麼，我可以說複雜性是O(n)還是O(n^2)？

注意：代碼片段是LeetCode.com中的一個問題的解決方案，該問題顯然具有一系列面試問題。

Answer 1

外環是O(N)。
內循環爲O(sqrt(i))。

總和將是：

1 + sqrt(2) + ... + sqrt(N) 

它比O(N)較大，但小於O(N^2)。

沒有進入上述總和的非常準確的計算，我會說，它接近O(N*sqrt(N))。

更新

從http://ramanujan.sirinudi.org/Volumes/published/ram09.pdf，上述款項是：

C1 + (2.0/3)*N*SQRT(N) + (1.0/2)*SQRT(N) + ....