algorithm - 使用大 O 表示法查找算法的时间复杂度

Question

我对这两个问题都有答案，但我对自己的工作不太有信心。有人可以检查一下并纠正任何错误吗？

for (i = 1; i <= n; i++) {
    for (j = 2*i; j <= n; j++) {
        puts("hello");
    }
} 

我的答案:1+(N+1)+N+N[1+((N+1)+N+N[1])/2] = 3/2N^2+7/2N+2 = O(N^2)

它说 j=2*i 的部分真的让我失望，我的思考过程是在 j=2*i 之后，其余代码只执行一半，因为它比 N 快两倍如果 j 等于 i 的情况。

for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
        for (k = 1; k <= 200; k++) {
            printf("%d %d\n", i, j);
        }
    }
} 

我的答案:1+(N+1)+N+N[1+(N+1)+N+N[1+201+200+200[1]]] = 604N^2+4N+2 = O(N^2)

我觉得这应该是 O(N^3)，因为它是一个三重嵌套循环，但我也认为它可能是 O(N^2)，因为最后一个循环进行了大约 200 次，而不是N次。

Answer 1

My answer [is] O(N²)

这是正确的。 j = 2*i 初始化跳到第一个索引的两倍，但嵌套循环仍以 1 进行，总体复杂度为 N²。

你的第二个答案也是正确的。尽管第三个嵌套循环增加了 200 次迭代，但这个数字是一个常数，因此它从大 O 渐近复杂度结果中“分解”出来。