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

Question

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

我可以肯定该算法至少需要 O(n) 因为 for，但我不知道如何处理。我知道在这种情况下我必须评估最差的 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

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

如果另一方面 j mod 2 == 0（所以 j 是 even），那么我们减少 j。现在有两种情况可能发生，i == j，在这种情况下我们不执行额外的迭代。但是，如果我们执行额外的迭代，if 条件将失败，因为递减 even 数字会导致 odd 数字。由于我们每次都设置j = n，也就意味着while循环执行的步数是由n本身决定的。

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

由于我们执行 while 循环恰好 n 次，因此这意味着算法仍然是 O(n) 。我们在这里假设我们可以检查一个数字的奇偶校验并在常数时间内递减一个数字。

Answer 2

mod是指模数吗？在这种情况下，while 循环将最多评估两次；一次递减 j，但随后 j mod 2 将变为 1，并且在设置 j=i 之后，您的 i<j 将为假。这里的复杂性差异随着输入的增加而振荡而不是增加，因此对于这个分支来说是 O(1)。

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

What is the complexity of this pseudo-code

algorithm

complexity-theory

pseudocode

time-complexity