c - 这两个循环的时间复杂度是多少？

Question

对于这两个 while 循环，我想计算出大 O 的复杂度。不详细，只是给出这些选项:(O(log N), O(sqrt(N), O(N), O(N log N), O(N·N)。这是一个老考试问题，我找不到答案。

问题 1

int i, j = N;
while (i < j) {
  i += 2 * j + 1;
  j++;
} 

问题 2

int i = 1, j = N;
while (i < j) {
  i += i;
  j--;
}

第一个问题的答案应该是 O(N·N)，第二个问题的答案是 O(log(N))。如果有人能够对答案进行解释，那就太好了。

Answer 1

第一个，如果 i>=j，则 O(1)。如果i和j为正，则循环一次，结束O(1)。

如果 i 为负数且 j 不为(>= 0)，您将看到 i 从 i 缓慢增长到 0，然后当 i 为正数时循环停止。在这种情况下，我至少增长了 N/2。

如果 i 和 j 都是非常大的负数，则 i 会变得更加负，直到 j 达到 0。在此期间，i 会变得更加负，至少每次都会增加 abs(j)，即 O(N * N)。当 j 达到 0 时，它已经是 O(N * N)，所以即使一旦 j==0 确实很快，答案也应该是 O(N * N)。

对于最后一种情况，i 遵循如下序列(假设 Z 是大于 abs(N) 的正数):

-Z、-Z-2Z+1、-Z-2Z+1-2(Z-1)+1、-Z-2Z+1-2(Z-1)+1-2(Z-2) )+1 ....(直到 j 达到 0).. 然后达到粗略幅度 Z 平方的某个最大负数(例如 W).. 然后变成 W+2+1, W+2+1+4+1 ，W+2+1+4+1+6+1 ...直到 i>j。

因此，在最坏的情况下，对于所有情况，第一个问题都是 O(N*N)。

第二个每次都会将 i 加倍，O(log N) 也是如此。想象一下，如果 j 是一个非常大的数字 1000000，并且 i = 1。那么 (i, j) 将是 (2, 999999), (4, 999998), (8, 999997, (16...) (32, ) (64, ) (128, ) (256, ) (512, ) (1024, ) (2048, ) (4096, ) (8192, ) (16384, ) (32768, ) (65536, ) (131092, ) (262144 , ) (524288, 999981)，需要 19 个步骤。