理解一个线性运行时实现的字谜检测
我正在学习算法分析（python 2.7.6）。 我正在阅读一本书（用算法和数据结构解决问题），其中Python是用于实现的语言。 在第2章中，作者以一种非常清楚易懂的方式介绍了算法分析，并使用一个谚语检测程序作为模板来比较不同的运行时实现（二次曲线，对数线性，线性）。 在线性和最有效的实现中，代码如下（我添加了注释）：
def anagram_test2(s1,s2):
""" Checks if two strings are anagrams of each other
Runs with O(n) linear complexity """
if (not s1) or (not s2):
raise TypeError, "Invalid input: input must be string"
return None
# Initialize two lists of counters
c1 = [0] * 26
c2 = [0] * 26
# Iterate over each string
# When a char is encountered,
# increment the counter at
# its correspoding position
for i in range(len(s1)):
pos = ord(s1[i]) - ord("a")
c1[pos] += 1
for i in range(len(s2)):
pos = ord(s2[i]) - ord("a")
c2[pos] += 1
j = 0
hit = True
while j < 26 and hit:
if c1[j] == c2[j]:
j += 1
else:
hit = False
return hit
我的问题是：两个for循环之后的代码块是否可以不被简单代替：
if c1 == c2:
return True
else:
return False
return
没有迭代是必要的（与使用while语句相反）？ 使用第一种方法还是第二种方法存在一些计算/编程原因？ 我在各种字符串组合上运行这个版本，它的工作原理完全相同。
还有一个更一般的问题：作者的意思是嵌套迭代会导致二次运行，而非嵌套迭代会导致线性/对数/对数线性运行时。 是否有一套明确的规则来确定算法的运行时间？ 例如，如何区分给定一个没有嵌套迭代的程序的线性/对数线性/对数算法？ 在上面发布的示例之前的那个示例中，作者使用了一个排序和比较实现，其中没有嵌套循环，但承认排序方法具有自己的成本，它可以是对数线性或二次方。
是的，所有这些代码都在检查两个数组是否相等。 要做到这一点，你只需要return c1 == c2
是否有一套明确的规则来确定算法的运行时间找出算法的运行时间是一个复杂的过程，但可能有几个快捷方式。 一些快捷键是：
k从一个常数运行到n常量递增的嵌套循环将运行在O(n^k) n ，你乘以一个常量将运行在O(log(n)) PS与你的问题无关，但整个功能可以用一个计数器代替。
from collections import Counter
def isAnagram(s1, s2):
return Counter(s1) == Counter(s2)
在python中你可以做c1 == c2 ，但其他语言需要循环，这就是作者试图展示的内容。
在python中，单行代码对每个索引执行隐式循环以检查是否相等。
看起来作者正试图按照O（1）操作来阐明算法（当试图找出整体运行时复杂性时，这是有意义的）。
c1 == c2 （其中c1和c2是列表）隐藏了一点复杂性; 它实际上更像len(c1) == len(c2) and all(ch1 == ch2 for ch1,ch2 in zip(c1, c2)) 。 他展示了比较中涉及的基本操作。
上一篇: Understanding a linear runtime implementation of anagram detection
下一篇: What exactly does O(n) space complexity mean and how inefficient is it?