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