问题描述
我正在通过比较提供的anagram算法来研究数量级。
我正在使用IPython的%timeit magic来测试这些功能。
解决方案如下。
第一个算法：
# 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
第二个算法：
# Count and Compare
def anagram_solution4(s1, s2):
c1 = [0] * 26
c2 = [0] * 26
for i in range(len(s1)):
pos = ord(s1[i]) - ord('a')
c1[pos] = c1[pos] + 1
for i in range(len(s2)):
pos = ord(s2[i]) - ord('a')
c2[pos] = c2[pos] + 1
j = 0
still_ok = True
while j < 26 and still_ok:
if c1[j] == c2[j]:
j = j + 1
else:
still_ok = False
return still_ok
排序和比较功能（解决方案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
也许我遗漏了一些基本的东西，但为什么线性解决方案需要比二次/对数线性解决方案更长的时间？
编辑
为了完整起见，我将包含的图表。
在较低的“x”值处，对数线性和线性曲线似乎存在交叉点。
1楼
请记住，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个字符才能赶上，但从那时起它将是更快的算法。
2楼
O[N]和O[N^2]是关于缩放的，而不是关于绝对时间。
例如， O[N]算法可能需要10秒10点，100秒100点，1000点1000秒等。
O[N^2]算法可能需要10ms用于10个点，1秒用于100个点，100秒用于1000个点等。
请注意， O[N^2]算法在时钟时间的意义上比O[N]快，但缩放比例不同。
O[N]测量时间随着N的增加而变化，而不是算法所花费的时间量。
3楼
已经有3个很好的答案了，但我认为这会增加一个略有不同的视角。
一般而言，大符号实际上只表示较低阶算法在某些时刻比较高阶算法更快 。
Big O本身绝对没有关于何时该信息的信息。
它可以是N=3或N=10^1000 。
话虽如此，对于实际算法，它倾向于在N = 100万左右之前发生，并且经常在N超过10,000左右之前发生。 在较小的输入（N <10左右）的情况下，通常情况是最简单的算法是最快的而不管大O，只要算法是现实的，不像 。
可以用不同的运输工具来驱动类比。 为了增加旅行距离，反过来最有效的方法是：徒步 - 自行车 - 汽车 - 火车 - 飞机。 对于较小的距离，每一个都比前一个更糟糕，但最终开始表现优于它。
这导致了另一个结论： 更简单，但“更慢”的算法具有完全的权利存在，并且如果您的数据大小位于更有效的段中，则选择“更快”的算法。 这是另一个问题，你不可能预测你的数据有多大，特别是如果它是一个软件库。 这就是为什么通常选择“最新和最好”的原因，或者如果选择单个方法的权衡足够大，则代码在几种方法之间交替。
4楼
常量！
线性解决方案可能是这样的
t_linear = c0 + c1 * N
另一个可能是这样的
t_square = d0 + d1 * N + d2 * N**2
c和d的常数是常数。
让设置c0 = 100, c1 = 1; d0 = 1, d1 = 0 and d2 = 1 c0 = 100, c1 = 1; d0 = 1, d1 = 0 and d2 = 1
那么对于小N，比如N = 4我们得到t_linear = 104和t_square = 17，即t_linear > t_square
当N增加然后t_square接近然后超过t_linear，即对于N = 11我们得到t_linear = 111和t_square = 122，即t_linear < t_square
我想现代的CPU架构如果达到缓存限制也会犯规; 操作系统可以被操纵以识别基准并且支持一个例子而不是另一个例子; ...... 但常数是更可能的原因。