查找算法

Question

递推方程我必须找到从该算法递推方程：

ALGO(n) 
    if n <= 2 then return(0) 
    else 
     y = ALGO(n/3) 
     i = 2^n 
     while i >= 2 do 
      j = (1/2) * log(i) //base 2 
      while j > 0 do 
       i = i/2 
       j = j - 1 
     z = ALGO(n/2) 
     return(z+y) 

我推断关于它并得出结论认为 T（N）= O（1）如果n < = 2

我认为inner while是一个O（n）（j在每次迭代时减少1），而外部while是O（logn）（每次迭代时i减半），给出一个O（n * （n））：

如果n> 2，则T（n）= T（n/3）+ T（n/2）+ O（n * log（n））

这是一个很好的说法吗？

Answer 1

两个while循环应该是O（N）：

1. i = 2^n; 
2. j = (1/2) * log (i) = 1/2 * n = n/2 
3. the inner while executes for n/2 times then j becomes 0, now i = i/2^(n/2) = 2^(n/2); 

现在，这一计划将回到步骤1，只有我一半。所以这两个循环应该是：

n/2+n/4+n/8+... = O(n) 

实际上，这也可以从更简单的角度来看。由于循环不会终止，直到i == 1，并且对于每个执行i = i/2，内循环将运行n次。想象一下，我们将内部循环和外部循环展平，将有n次i = i/2，因此两个循环是O（n）。总之，T（n）= T（n/3）+ T（n/2）+ O（n）。

希望这可能会有所帮助！