为什么IPython“%timeit”为O（n）解决方案生成的时间较慢？

Question

我正在通过比较interactivepython.org上提供的anagram算法来研究数量级。我使用IPython的%timeit魔术来测试这些函数。解决方法如下。第一种算法：

# Sort and Compare
def anagram_solution2(s1,s2):
    a_list1 = list(s1)
    a_list2 = list(s2)

    a_list1.sort()
    a_list2.sort()

    pos = 0
    matches = True

    while pos < len(s1) and matches:
        if a_list1[pos] == a_list2[pos]:
            pos = pos + 1
        else:
            matches = False
    return matches

第二种方法：

^{pr2}$

排序和比较函数（解决方案2）是高阶的，可以是O（n^2）或O（nlogn）解。计数和比较函数（解决方案4）被声明为O（n）解决方案，因此如果用%timeit进行测试，我希望时间更短。但是，我得到了以下结果：

%timeit anagram_solution2('conversationalists', 'conservationalists')
# 100000 loops, best of 3: 13 µs per loop

%timeit anagram_solution4('conversationalists', 'conservationalists')
# 10000 loops, best of 3: 21 µs per loop

也许我遗漏了一些基本的东西，但为什么线性解比二次/对数线性解耗时更长呢？在

编辑

为了完整起见，我包含了一个common Big-O functions的图。在较低的“x”值下，对数线性曲线和线性曲线似乎存在交叉点。

Answer 1

O[N]和O[N^2]是关于缩放的，而不是关于绝对时间的。例如，O[N]算法可能需要10秒来获得10个点，100个点需要100秒，1000个点需要1000秒，等等

一个O[N^2]算法可能需要10毫秒，100个点需要1秒，1000个点需要100秒，等等

注意这里的O[N^2]算法比O[N]算法要快得多，但缩放比例不同。在

O[N]衡量时间如何随着N的增加而变化，而不是算法所花费的时间。在

Answer 2

已经有3个很好的答案，但我认为这增加了一个稍微不同的视角。在

一般来说，大记数法实际上只说明在某个时刻低阶算法比高阶算法快。大O本身绝对没有提供任何关于何时到达的信息。它可以是N=3或{}。在

也就是说，对于实际的算法来说，它往往发生在N=100万左右之前，而且往往在N超过10000之前。在较小的输入（N<；10左右）的情况下，通常情况下，不管大O是什么，最简单的算法都是最快的，只要算法是实际的，不像Bogosort。在

可以用不同的交通工具进行类比。为了增加旅行距离，最有效的方法依次是：步行-自行车-汽车-火车-飞机。在距离较短的情况下，每一种方法都比前一种方法更差，但最终会表现得更好。在

这导致了另一个结论：如果您的数据大小在更有效的数据段中，则更简单但“较慢”的算法拥有完全存在的权利，并被选中而不是“更快的”算法。这是另一个问题，您不可能预测您的数据会有多大，尤其是当它是一个软件库时。这就是为什么通常选择“最新和最棒”的方法，或者如果选择单个方法的权衡足够大的话，代码会在几个方法之间交替。在

Answer 3

请记住，O（）表示法只引用了整个时间方程的支配项。例如，O（n）可能是指一个需要1000*n+7000秒的进程；一个竞争的O（n^2）进程可能是0.5*n^2+.10秒。N必须非常大，N^2进程才能在更短的时间内运行。在

在本例中，O（n）算法通过三个单独的n长度循环，并抛出两个操作。这会使N的小值变慢。我将运行几个测试。。。在

---

我试过用两个字母，然后是一个字母表的副本，然后是30个副本：

length 2    O(n^2) 1.00135803223e-05    O(n) 1.50203704834e-05
length 26   O(n^2) 1.69277191162e-05    O(n) 2.59876251221e-05
length 780  O(n^2) 0.000540971755981    O(n) 0.00049901008606

在我的环境中，O（n）算法可能要到500个字符才能赶上，但从那时起它将是更快的算法。在