时间戳

首页 > 解决方案 > 这个伪代码的复杂度是多少

algorithm - 这个伪代码的复杂度是多少

问题描述

我在考试中发现了这个练习，我遇到了解决问题的困难。

我可以肯定该算法至少需要 O(n) 的时间，但我不知道如何处理。我知道在这种情况下，我必须评估最差的 if-else 分支，并确保它是第二个。

for i=1...n do
    j=n
    while i<j do
        if j mod 2 = 0 then j=j-1
        else j=i

直觉上我认为总成本是：O(nlogn)=O(n)*O(logn)

标签： algorithmtime-complexitycomplexity-theorypseudocode

解决方案

简而言之：while循环每次最多运行两次迭代。这使得算法O(n)。

循环最多会while迭代两次。确实让我们看一下 while 循环：

while i < j do
    if j mod 2 = 0 then
        j=j-1
    else
        j=i

很明显，我们只会执行while循环 if i < j。此外，如果j mod 2 == 1（所以j是奇数），那么它将设置j = i，因此 while 循环将不再运行。

另一方面，如果j mod 2 == 0（偶数j也是如此），那么我们递减。现在有两件事可能发生，在这种情况下，我们不执行额外的迭代。但是，如果我们执行额外的迭代，则条件将失败，因为减少偶数会导致奇数。由于我们每次都设置了，也就意味着while循环执行的步数是由自己决定的。ji == jifj = nn

因此，这意味着无论 和 的值是什么i，循环j的主体while将最多执行两次。

由于我们准确地执行了while循环n，因此这意味着算法仍然是O(n)。我们在这里假设我们可以检查一个数字的奇偶性并在恒定时间内递减一个数字。

推荐阅读