两个独立的嵌套 while 循环的时间复杂度

Question

我刚开始我的数据结构课程，我在尝试计算以下代码的时间复杂度时遇到了麻烦：

{
  int j, y; 
  for(j = n; j >= 1; j--)
  { 
     y = 1; 
     while (y < j)
       y *= 2;
     while (y > 2) 
     y = sqrt(y); 
}

外'for'循环在代码的每个运行中运行ning n次，第一个'while'循环运行s关于log2 (j) 如果我没记错的话。
我不确定第二个 'while' 循环以及如何确定代码的整体时间复杂度。
我最初的想法是确定在 'for' 循环的每次迭代中哪个 'while' 循环会“花费”更多，只考虑两者中较高的一个并将其加起来，但显然它并没有引导我到一个答案。

希望得到任何帮助，尤其是在尝试计算此类代码的复杂性的过程和总体方法方面。

Answer 1

您说得对，第一个 while 循环具有时间复杂度 O(log(j))。第二个 while 循环在 y 上重复执行平方根，直到它小于 2.

由于 y 大约是 j（介于 j 和 2j 之间），问题是：您多久可以对 [=14 执行一次平方根=] 直到你得到一个小于或等于 2 的数字？但同样地，您可能会问：在得到大于或等于 j 的数字之前，您可以对 2 进行平方多少次？或者作为方程式：

    (((2^2)^...)^2 >= j    // k repeated squares
<=>        2^(2^k) >= j
<=>              k >= log(log(j))

所以第二个while循环的时间复杂度O(log(log(j))。与 O(log(j)) 相比，这可以忽略不计。现在因为 j <= n 并且循环迭代 n 次，我们得到整体复杂度 O(n log(n)).

两个独立的嵌套 while 循环的时间复杂度

Time complexity of two separate nested while loops

structure

time-complexity

data-structures