总和等于给定数 n 的最小平方数的时间复杂度

Question

这段代码的确切时间复杂度是多少？

我知道它的指数，但什么样的指数，如 2^n 、sqrt(n( ^ sqrt(n( 等。

如果附上一些证据，那就太好了。

https://www.geeksforgeeks.org/minimum-number-of-squares-whose-sum-equals-to-given-number-n/

class squares { 
// Returns count of minimum squares that sum to n 
static int getMinSquares(int n) 
{ 
// base cases 
if (n <= 3) 
return n; 
// getMinSquares rest of the table using recursive 
// formula 
int res = n; // Maximum squares required is 
// n (1*1 + 1*1 + ..) 
// Go through all smaller numbers 
// to recursively find minimum 
for (int x = 1; x <= n; x++) { 
int temp = x * x; 
if (temp > n) 
break; 
else
res = Math.min(res, 1 + getMinSquares(n - temp)); 
} 
return res; 
} 
public static void main(String args[]) 
{ 
System.out.println(getMinSquares(6)); 
} 
} 

在我看来，由于每个 for 循环都在调用相同的递归 sqrt(n( 时间数，并且每个调用都是 for (n - x*x(( ~ n...

所以它应该是 n ^ sqrt(n(。

这个答案正确吗？

Answer 1

该函数的递归关系为

T(n) = sum from i=1 to i=sqrt(n) of T(n - i*i)

上面以

T(n) = sqrt(n) * T(n-1)

因为上述总和中的每个术语最多都是T(n-1)并且有sqrt(n)。T(n) = sqrt(n) * T(n-1)O( sqrt(n)^n ).我确信有一些聪明的方法可以获得更好的边界，但这个函数看起来像是指数级的。