python - 线性时间与二次时间

Question

通常，一些答案提到给定解决方案是线性，或者另一个解决方案是二次。

如何区分/识别什么是什么？

谁能为像我这样仍然不知道的人解释一下这个最简单的方法？

Answer 1

一个方法是线性的，当它所花费的时间随着所涉及的元素数量线性增加。例如，打印数组元素的 for 循环大致是线性的:

for x in range(10):
    print x

因为如果我们打印 range(100) 而不是 range(10)，运行它所需的时间会长 10 倍。你会经常看到写成 O(N)，这意味着运行算法的时间或计算量与 N 成正比。

现在，假设我们要打印两个 for 循环的元素:

for x in range(10):
    for y in range(10):
        print x, y

对于每个 x，我循环 10 次 y。出于这个原因，整个事情要经过 10x10=100 次打印(您只需运行代码即可看到它们)。如果我不使用 10，而是使用 100，那么现在该方法将执行 100x100=10000。换句话说，该方法采用 O(N*N) 或 O(N²)，因为每次增加元素数量时，计算工作量或时间都会随着点数的平方而增加。