algorithm - Big-O 的运行时间

Question

我在完全理解 Big-O 符号以及嵌套循环如何影响运行时间时遇到了一些困难。我知道嵌套循环的时间复杂度等于最内层语句的执行次数，但我只是想检查一下我的理解。

1

count=1
for i=1 to N
    for j=1 to N
        for k=1 to N
            count+=1

因为有 2 个嵌套循环，所以它是 O(N³)，对吗？

---

2

count=1
for i=1 to N^2
    for j=1 to N
        count+=1

外循环迭代N²，内循环运行N次，这使得它O(N³)，对吧？

---

3

count=1
for (i=0;i<N;++i)
    for (j=0;j<i*i;++j)
        for (k=0;k<j;++k)
            ++count

这将是 O(N)，因为 N 仅在第一个 for 循环中被调用？

Answer 1

大 O 表示法描述了算法或程序如何根据输入量扩展性能(运行时间、内存要求等)。

例如:

• O(1) 表示无论数据量如何，它都需要常数时间
• O(N) 线性缩放:给它五倍的输入，它需要五倍的时间才能完成
• O(N^2) 以二次方式缩放:例如十倍的输入将花费一百倍的时间来完成

您的第三个示例是 O(N^4)，因为这是 N 的最内层迭代总数的比例。

对于这些简单的情况，您可以计算最内层的迭代次数，但肯定有比这更复杂的算法。