gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-11-30 19:41:22 25 4
gpt4 key购买 nike

对于这两个 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))。如果有人能够对答案进行解释,那就太好了。

最佳答案

第一个,如果 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 个步骤。

关于c - 这两个循环的时间复杂度是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33633003/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com