了解变位词检测的线性运行时实现

Question

我正在学习算法分析（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 语句相反）？使用第一种方法与第二种方法有一些 computational/programmatic 原因吗？我运行这个版本在各种字符串组合上都完全一样。

还有一个更笼统的问题：作者有点暗示嵌套迭代会导致二次运行时间，而非嵌套迭代会导致 linear/logarithmic/log 线性运行时间。是否有一套独特的规则来确定算法的运行时间？例如，给定一个没有嵌套迭代的程序，如何区分 linear/log linear/log 算术算法？在我上面发布的示例之前的示例中，作者使用了一种没有嵌套循环的排序和比较实现，但承认排序方法有其自身的成本，即对数线性或二次。

Answer 1

是的，这段代码所做的就是检查两个数组是否相等。为此，您只需 return c1 == c2

Is there a distinct set of rules for determining an algorithm's runtime Figuring out the runtime of the algorithm is a complex procedure, but there can be a couple of shortcuts. Some of the shortcuts are:

k 从常数运行到 n 以常数递增的运行嵌套循环将在 O(n^k)
一个从常数运行到 n 的循环，你乘以一个常数将运行 in O(log(n))
如果你有递归（这发生在很多分而治之的算法中），你可以使用 masters theorem. For really hard recursions there is a Bazzi method.

P.S. 与您的问题无关，但整个功能可以只用 counter.

代替

from collections import Counter
def isAnagram(s1, s2):
    return Counter(s1) == Counter(s2)

Answer 2

在python中你可以做c1 == c2，但是其他语言需要一个循环，这就是作者试图展示的。

在 python 中，那一行代码对每个索引执行隐式 for 循环以检查是否相等。

Answer 3

看起来作者正试图根据 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

python

algorithm

big-o