算法的渐近复杂度 [英] Asymptotic Complexity for an Algorithm

问题描述

i <-- 0
while(i < n)  
    someWork(...)
    i <-- i^2
done

如果满足以下条件，有人可以确认此循环的最坏情况时间复杂度(Big-O)为O(log n):

Can someone confirm that the worst case time complexity (Big-O) of this loop is O(log n) if:

1. someWork(...)是O(1)算法

someWork(...)是O(n)算法

此外，如果someWork(...)精确地执行i操作，最坏情况下的时间复杂度(Big-O)是什么? someWork(...)随着i的增加而做的工作更多.您的答案应该类似于sigma(f(i)).

Also, what is the worst case time complexity (Big-O) if someWork(...) does exactly i operations? someWork(...) does more work as i increases. Your answer should be something like sigma(f(i)).

非常感谢您的帮助.

推荐答案

首先:如果(如上所述)0 <= i <= 1成立，该算法将永远不会终止.

First: if (as mentioned) 0 <= i <= 1 holds, the algorithm will never terminate.

所以:让i > 1.

在循环的每一轮中，i的指数将加倍.因此，在第k轮中，数字将为i^(2^k).只要i^(2^k) < n成立，循环就会一直持续下去，这等效于k < log log n.确实是log_2 log_i n，但是由于所有对数均等于常数，因此我只写log log n. 通知:如果i不是常数，则必须将1/log log i乘以复杂度.

In every round of the loop the exponent of i will be doubled. So in the k-th round the number will be i^(2^k). The loop keeps going as long as i^(2^k) < n holds, which is equivalent to k < log log n. Exactly it is log_2 log_i n, but due to all logarthms are equal exept for a constant factor, I just write log log n. Notice: if i is not constant, 1/log log i has to be multiplied to the complexity.

所以算法的复杂度是

1. O(log log n)(如果someWork()位于O(1)
中)
2. O(n log log n)，如果someWork()在O(n)
中

1. O(log log n), if someWork() is in O(1)
2. O(n log log n), if someWork() is in O(n)

如果someWork()在k回合中执行O(i^(2^k))个操作，则总复杂度为

If someWork() does O(i^(2^k)) operations in round k you get a total complexity of

O( i + i^2 + i^(2^2) + i^(2^3) + ... + i^(2^(log log n)) ) 

如果i是常数，则简化为O(i * i^(2^(log log n)) ) = O(i * n)或O(n).

This simplifys to O(i * i^(2^(log log n)) ) = O(i * n) or O(n) if i is constant.

要查看简化，请查看以下内容:
数字i + i^2 + i^4 + i^8可以用i -ary形式写为 100 010 110.所以你可以看到

To see the simplification take a look at the following:
The number i + i^2 + i^4 + i^8 can be written in i-ary as 100 010 110. So you can see that

i + i^(2^1) + i^(2^2) + ... + i^(2^k) < i * i^(2^k)

成立，因为它等于100 010 110 < 1 000 000 000.

修改:
我不确定您用sigma表示法是什么意思，但也许是这样的:

Edit:
I'm not sure what you mean by sigma notation but maybe it is this:

这篇关于算法的渐近复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！