下面的代码片段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) + ....