关于平方根的时间复杂度问题

Question

我正在尝试回答以下问题：

Given n=2k find the complexity

func(n)

if(n==2) return1;

else n=1+func(sqrt(n))

end

我想因为有if-else语句，肯定会循环n次，但我对func(sqrt(n))的递归循环感到困惑。由于它是平方根的，我认为时间复杂度是

O(sqrt(n) * n) = O(n^1/2 * n) = O(n^3/2) = O(2k^3/2)。然而，可能的答案选择只有

O(k)
O(2^n)
O(n*k)

O(2k^3/2)可以算作O(k)吗？我很困惑，因为虽然时间复杂度经常被简化，但 O(n) 和 O(n^2) 是不同的，所以我认为 O(2k^3/2) 只能简化为 O(k^3/2) .

Answer 1

我认为这里的 none 答案是这个问题的最佳答案。

如果你有一个递归函数，它每次迭代的复杂度为 O(1)，然后将其参数的大小从 n 减小到 √n，就像这里的情况，the runtime works out to O(log log n)。这背后的直觉是，对一个数求平方根会丢弃该数的一半数字，大致而言，因此运行时间将为 O(log d)，其中 d 是输入数字的位数。数字 n 的位数为 O(log n)，因此整体运行时间为 O(log log n)。

在你的例子中，你有 n = 2k，所以 O(log log n) = O(log log k)。（除非你的意思是 n = 2^k，在这种情况下 O(log log n) = O(log log 2^k) = O(log k).)

注意我们没有得到 O(n × √n) 作为我们的结果。如果我们做 O(√n) 次 O(n) 次，就会发生这种情况。但在这里，这不是我们正在做的。输入的大小在每次迭代中缩小平方根，但这与说我们正在做平方根的工作量不同。而且这种情况发生的次数不是 O(n)，因为 n 的值缩小得太快了。

以此类推，此代码的运行时间为 O(log n)，而不是 O(n × n / 2):

func(n):
    if n <= 2 return 1
    return func(n/2)

关于平方根的时间复杂度问题

Time Complexity Question about Square Roots

big-o

time-complexity