Python 线性时间 vs 二次时间
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/18023576/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Linear time v.s. Quadratic time
提问by Anthony Perot
Often, some of the answers mention that a given solution is linear, or that another one is quadratic.
通常，一些答案提到给定的解决方案是线性的，或者另一个是二次的。
How to make the difference / identify what is what?
如何区分/识别什么是什么？
Can someone explain this, the easiest possible way, for the ones like me who still don't know?
有人可以为像我这样仍然不知道的人解释这一点，最简单的方法吗？
采纳答案by Jblasco
A method is linear when the time it takes increases linearly with the number of elements involved. For example, a for loop which prints the elements of an array is roughly linear:
当一个方法所花费的时间随着涉及的元素数量线性增加时，它就是线性的。例如，打印数组元素的 for 循环大致是线性的：
for x in range(10):
print x
because if we print range(100) instead of range(10), the time it will take to run it is 10 times longer. You will see very often that written as O(N), meaning that the time or computational effort to run the algorithm is proportional to N.
因为如果我们打印 range(100) 而不是 range(10)，运行它所需的时间会长 10 倍。你会经常看到写成 O(N)，这意味着运行算法的时间或计算工作量与 N 成正比。
Now, let's say we want to print the elements of two for loops:
现在，假设我们要打印两个 for 循环的元素：
for x in range(10):
for y in range(10):
print x, y
For every x, I go 10 times looping y. For this reason, the whole thing goes through 10x10=100 prints (you can see them just by running the code). If instead of using 10, I use 100, now the method will do 100x100=10000. In other words, the method goes as O(N*N) or O(N2), because every time you increase the number of elements, the computation effort or time will increase as the square of the number of points.
对于每个 x，我循环 y 10 次。出于这个原因，整个过程需要进行 10x10=100 次打印（您只需运行代码即可看到它们）。如果我不使用 10，而是使用 100，那么现在该方法将执行 100x100=10000。换句话说，该方法是 O(N*N) 或 O(N2)，因为每次增加元素数量时，计算工作量或时间都会随着点数的平方而增加。
回答by Ralph Caraveo
They must be referring to run-time complexity also known as Big O notation. This is an extremely large topic to tackle. I would start with the article on wikipedia: https://en.wikipedia.org/wiki/Big_O_notation
它们一定是指运行时复杂性，也称为 Big O 表示法。这是一个非常大的话题。我将从维基百科上的文章开始：https: //en.wikipedia.org/wiki/Big_O_notation
When I was researching this topic one of the things I learned to do is graph the runtime of my algorithm with different size sets of data. When you graph the results you will notice that the line or curve can be classified into one of several orders of growth.
当我研究这个主题时，我学到的一件事就是用不同大小的数据集绘制算法的运行时间。当您绘制结果图时，您会注意到直线或曲线可以归类为几个增长顺序之一。
Understanding how to classify the runtime complexity of an algorithm will give you a framework to understanding how your algorithm will scale in terms of time or memory. It will give you the power to compare and classify algorithms loosely with each other.
了解如何对算法的运行时复杂性进行分类将为您提供一个框架，以了解您的算法将如何在时间或内存方面进行扩展。它将使您能够对算法进行松散的比较和分类。
I'm no expert but this helped me get started down the rabbit hole.
我不是专家，但这帮助我开始了兔子洞。
Here are some typical orders of growth:
以下是一些典型的增长顺序：
- O(1) - constant time
- O(log n) - logarithmic
- O(n) - linear time
- O(n^2) - quadratic
- O(2^n) - exponential
- O(n!) - factorial
- O(1) - 常数时间
- O(log n) - 对数
- O(n) - 线性时间
- O(n^2) - 二次
- O(2^n) - 指数
- O(n!) - 阶乘
If the wikipedia article is difficult to swallow, I highly recommend watching some lectures on the subject on iTunes University and looking into the topics of algorithm analysis, big-O notation, data structures and even operation counting.
如果维基百科的文章难以下咽，我强烈建议您在 iTunes 大学观看一些有关该主题的讲座，并研究算法分析、大 O 表示法、数据结构甚至操作计数等主题。
Good luck!
祝你好运！
回答by Femaref
You usually argue about an algorithm in terms of their input size n(if the input is an array or a list). A linear solution to a problem would be an algorithm which execution times scales lineary with n, so x*n + y, where xand yare real numbers. nappears with a highest exponent of 1: n = n^1.
您通常会根据输入大小n（如果输入是数组或列表）来讨论算法。问题的线性解决方案是一种算法，其执行时间与n、 所以x*n + y、x和y是实数成线性比例。n出现的最高指数为 1: n = n^1。
With a quadratic solution, nappears in a term with 2 as the highest exponent, e.g. x*n^2 + y*n + z.
对于二次解，n出现在以 2 作为最高指数的项中，例如x*n^2 + y*n + z。
For arbitrary n, the linear solution grows in execution time much slower than the quadratic one.
对于任意n，线性解的执行时间增长比二次解慢得多。
For mor information, look up Big O Notation.
有关更多信息，请查找Big O Notation。
回答by mathematician1975
You do not specify but as you mention a solutionit is possible you are asking about quadratic and linear convergence. To this end, if you have an algorithm that is iterative and generates a sequence of approximations to a convergent value, then you have quadratic convergence when you can show that
您没有指定，但是当您提到解决方案时，您可能会询问二次和线性收敛。为此，如果您有一个迭代算法并生成一系列收敛值的近似值，那么当您可以证明时，您就有了二次收敛
x(n) <= c * x(n-1)^2
for some positive constant c. That is to say that the error in the solution at iteration n+1is less than the square of the error at iteration n. See this for a fuller introduction for more general convergence rate definitions http://en.wikipedia.org/wiki/Rate_of_convergence
对于一些正常数c。也就是说迭代时解的误差n+1小于迭代时误差的平方n。有关更一般收敛率定义的更全面介绍，请参阅此内容http://en.wikipedia.org/wiki/Rate_of_convergence
