algorithm - 循环的递归关系

Question

问题是建立一个递归关系来找到算法给出的值。答案应该是 teta() 术语。

foo = 0;

for int i=1 to n do
    for j=ceiling(sqrt(i)) to n do
        for k=1 to ceiling(log(i+j)) do
             foo++

Answer 1

不完全确定，但这里有。

第二个循环执行1 - sqrt(1) + 2 - sqrt(2) + ... + n - sqrt(n) = n(n+1)/2 - n^1.5时间 =>O(n^2)次。请参阅此处进行讨论sqrt(1) + ... + sqrt(n) = O(n^1.5)。

我们已经确定第三个循环将获得触发O(n^2)时间。所以该算法渐近地等价于这样的：

for i = 1 to n do
    for j = 1 to n do
        for k = 1 to log(i+j) do
            ++foo

这导致 sum log(1+1) + log(1+2) + ... + log(1+n) + ... + log(n+n)。log(1+1) + log(1+2) + ... + log(1+n) = log(2*3*...*(n+1)) = O(n log n). 这乘以n，得到O(n^2 log n)。

所以你的算法也是O(n^2 log n)，Theta(n^2 log n)如果我没记错的话。