34

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

如何有所作为/确定什么是什么？

有人可以为像我这样仍然不知道的人解释这个最简单的方法吗？

4

4 回答 4

66

当所花费的时间随所涉及的元素数量线性增加时，该方法是线性的。例如，打印数组元素的 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²)，因为每次增加元素数量时，计算工作量或时间都会随着点数的平方而增加。

于 2013-08-02T18:22:20.787 回答
35

他们一定指的是运行时复杂性，也称为大 O 表示法。这是一个非常大的话题。我将从维基百科上的文章开始：https ://en.wikipedia.org/wiki/Big_O_notation

当我研究这个主题时，我学会做的一件事就是用不同大小的数据集绘制我的算法的运行时间。当您绘制结果时，您会注意到线或曲线可以分为几个增长顺序之一。

了解如何对算法的运行时复杂性进行分类将为您提供一个框架，以了解您的算法将如何在时间或内存方面进行扩展。它将使您能够对算法进行松散的比较和分类。

我不是专家，但这帮助我开始了兔子洞。

以下是一些典型的增长顺序：

  • O(1) - 恒定时间
  • O(log n) - 对数
  • O(n) - 线性时间
  • O(n^2) - 二次
  • O(2^n) - 指数
  • O(n!) - 阶乘

如果维基百科的文章难以下咽，我强烈建议在 iTunes 大学观看一些关于该主题的讲座，并研究算法分析、大 O 表示法、数据结构甚至操作计数等主题。

祝你好运！

于 2013-08-02T18:17:55.750 回答
1

n您通常会根据输入大小（如果输入是数组或列表）来争论算法。一个问题的线性解决方案将是一种算法，其执行时间与n, 所以x*n + y, wherex和y是实数成线性比例。n以 1 的最高指数出现：n = n^1。

对于二次解，n出现在以 2 为最高指数的项中，例如x*n^2 + y*n + z。

对于任意n，线性解的执行时间增长比二次解慢得多。

有关更多信息，请查找Big O Notation。

于 2013-08-02T18:20:40.293 回答
1

您没有指定，但当您提到解决方案时，您可能会询问二次和线性收敛。为此，如果您有一个迭代算法并生成一系列收敛值的近似值，那么当您可以证明时，您就具有二次收敛性

 x(n) <= c * x(n-1)^2

对于一些正常数c。也就是说，迭代时解中的误差n+1小于迭代时误差的平方n。有关更一般的收敛速度定义的更全面介绍，请参阅此http://en.wikipedia.org/wiki/Rate_of_convergence

于 2013-08-02T18:28:50.197 回答