大家好！昨天和一个准备编程面试的朋友聊天，想学习一些算法的基础知识。我们谈到了二次时间与线性时间算法的话题，我认为在这里写下它们会很有趣，因为避免二次时间算法不仅在面试中很重要——有时在现实生活中也很好知道！稍后我将快速解释什么是“二次时间算法”:)我们将讨论以下3件事：二次时间函数比线性时间函数慢很多有时二次算法可以转化为线性算法这是因为hashmap查找非常快（即时查找！）我尽量避免使用数学术语并专注于真实的代码示例以及它们到底有多快/多慢。目标问题：求两个列表的交集让我们讨论一个简单的面试题：求两个数字列表的交集。例如，intersect([1,2,3],[2,4,5])应该返回[2]。这个问题也有点现实——你可以想象一个真实的程序，它的要求是取两个ID列表的交集。“显而易见”的解决方案：让我们编写一些代码来获取2个列表的交集。下面是实现此要求的程序，名为quadratic.py。importsys#实际运行的代码defintersection(list1,list2):result=[]forxinlist1:foryinlist2:ifx==y:result.append(y)returnresult#一些样板文件，这样我们可以借鉴在命令行运行程序来处理不同大小的列表defrun(n):#定义两个有n+1个元素的列表list1=list(range(3,n))+[2]list2=list(range(n+1,2*n))+[2]#取交集并输出结果print(list(intersection(list1,list2)))#使用第一个命令行参数作为输入，运行程序run(int(sys.argv[1]))程序之所以叫quadratic.py（LCTT：“quadratic”是“quadratic”的意思）的原因是：如果list1和list2的大小为n，那么内层循环（如果x==y)将运行n^2次。在数学中，像x^2这样的函数被称为“二次”函数。quadratic.py有多慢？使用多个不同长度的列表运行这个程序，两个列表的交集总是相同的：[2]。$timepython3quadratic.py10[2]real0m0.037s$timepython3quadratic.py100[2]real0m0.053s$timepython3quadratic.py1000[2]real0m0.051s$timepython3quadratic.py10000#10,000[2]real0m1.661s到目前为止一切顺利-该程序仍然需要不到2秒。然后在两个100,000个元素的列表上运行程序，我不得不等待很长时间。结果如下：$timepython3quadratic.py100000#100,000[2]real2m41.059s这可以说是相当慢了！总共花费了160秒，比在10,000个元素（1.6秒）上运行时快了近100倍。所以我们可以看到，在某个点之后，每将列表扩展10倍，程序的运行时间就会增加大约100倍。我没有尝试在1,000,000个元素上运行它，因为我知道它会再花100倍的时间——可能大约3个小时。我没有时间做这个！您现在大致了解了为什么二次时间算法会成为一个问题——即使是这个非常简单的程序也会很快变得非常慢。快速版：linear.py好了，我们来写一个快速版的程序。我会先给你看这个程序长什么样子，然后再分析它。importsys#实际算法defintersection(list1,list2):set1=set(list1)#这是一个哈希集result=[]foryinlist2:ifyinset1:result.append(y)returnresult#Some样板，因此我们可以从命令行运行程序并处理不同大小的列表defrun(n):#定义两个包含n+1个元素的列表list1=range(3,n)+[2]list2=range(n+1,2*n)+[2]#输出交集结果print(intersection(list1,list2))run(int(sys.argv[1]))（这不是使用Python最惯用的方式，但我think写代码尽量不用太多Python思想，让不懂Python的人更容易看懂）这里我们做了两件与慢版程序不同的事情：将list1转换成asetnamedset1only使用一个for循环而不是两个来查看linear.py程序有多快。在讨论这个程序为什么快之前，让我们先在一些大列表上运行这个程序来证明它确实很快。下面是程序在大小为10到10,000,000的列表上按顺序运行的演示。（记住，我们上一个程序在100,000个元素时开始变得非常非常慢）$timepython3linear.py100[2]real0m0.056s$timepython3linear.py1000[2]real0m0.036s$timepython3linear.py10000#10,000[2]real0m0.028s$timepython3linear.py100000#100,000[2]real0m0.048s<--quadratic.py在这种情况下用了2分钟！我们现在在0.04秒内完成！！！很快！$timepython3linear.py1000000#1,000,000[2]real0m0.178s$timepython3linear.py10000000#10,000,000[2]real0m1.560slinear.py实际上遇到了另一个问题如果我们试图在一个非常，非常大的列表（100亿/10,000,000,000个元素）：它足够快（列表只需要4.2秒到100倍大，所以我们大概应该在不超过420秒内完成），但是我的电脑没有足够的内存来存储列表的所有元素，因此程序在运行结束前崩溃。$timepython3linear.py10000000000Traceback（最近调用最后一次）：文件“/home/bork/work/homepage/linear.py”，第18行，在
