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

Question

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

由于 for，我可以肯定该算法至少需要 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)

Answer 1

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

while循环最多迭代两次。让我们来看看 while 循环:

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

很明显我们只会执行while循环如果 i < j .此外，如果 j mod 2 == 1 (所以 j 是奇数)，然后它将设置 j = i ，因此 while 循环将不再运行。

如果另一方面j mod 2 == 0 (所以 j 是偶数)，然后我们递减 j .现在有两件事可能发生，或者i == j ，在这种情况下我们不执行额外的迭代。然而，如果我们执行额外的迭代，if条件将失败，因为递减一个偶数数会导致一个奇数数。因为我们每次都设置j = n , 这也意味着 while 循环执行的步骤数由 n 决定本身。

这意味着无论 i 的值是什么和 j是，while 的正文循环最多执行两次。

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