线性时间与二次时间

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²）的形式，因为每次您增加元素数量时，计算工作量或时间将随点数的平方增加。