这个伪代码的复杂性是什么

Question

我在考试中发现了这种专长，遇到解决问题的困难。

我可以确定该算法至少会占用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（so j为奇数），则它将置位j = i，因此while循环将不再运行。

另一方面j mod 2 == 0（如果j是偶数），则我们递减j。现在可能发生两件事i == j，在这种情况下，我们不会执行额外的迭代。但是，如果我们执行额外的迭代，则if条件将失败，因为递减偶数会导致奇数。由于我们每次设置时间j = n，因此这也意味着while循环执行的步骤数由其n自身确定。

因此，这意味着不管什么价值观i和j是，在体内while循环将最多为2次进行。

由于我们执行了两次while循环n，因此这意味着算法仍为O（n）。在此我们假设可以检查数字的奇偶性并在固定时间内递减数字。