代码之家  ›  专栏  ›  技术社区  ›  Spectre

用big-O表示法求算法的时间复杂度

  •  2
  • Spectre  · 技术社区  · 8 年前

    我对这两个问题都有答案,但我对自己的工作不是很有信心。有人能检查一下并改正错误吗?

    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*我真的很反感,我的思维过程是,在j=2*i之后,其余代码的执行量只有一半,因为与j等于i的情况相比,它的速度将超过N的两倍。

    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次。

    1 回复  |  直到 8 年前
        1
  •  1
  •   Sergey Kalinichenko    8 年前

    我的回答是“否” 2. )

    这是正确的。 j = 2*i 初始化跳到第一个索引的两倍,但嵌套循环仍会继续 1 对于总N 2. 复杂性

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