了解线性运行时实现的字谜检测

我正在学习有关算法的分析（Python 2.7.6）。我正在阅读一本书（用算法和数据结构解决问题），其中Python是用于实现的语言。在第2章中，作者以一种非常清楚易懂的方式介绍了算法分析，并使用一个谚语检测程序作为模板来比较不同的运行时实现（quadratics，log linear，linear）。在线性，最有效的实现，代码如下（由我添加的注释）：了解线性运行时实现的字谜检测

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语句相反）？使用第一种方法还是第二种方法存在一些计算/编程原因？我在各种字符串组合上运行这个版本，它的工作原理完全相同。

还有一个更一般的问题：作者暗示嵌套迭代会导致二次运行，而非嵌套迭代会导致线性/对数/对数线性运行时。是否有一套明确的规则来确定算法的运行时间？例如，如何区分给定一个没有嵌套迭代的程序的线性/对数线性/对数算法？在上面发布的示例之前的那个示例中，作者使用了一个排序和比较实现，其中没有嵌套循环，但承认排序方法具有自己的成本，它可以是对数线性或二次方程。

来源

2015-12-07 Spyros

是，甚至只是：'return c1 == c2' – 101

是的，所有这些代码都是检查两个数组是否相等。而要做到这一点，你可以做到这return c1 == c2

是否有确定算法的运行时间搞清楚该算法的运行一组不同的规则是一个复杂的过程，但可以有几个快捷键。一些快捷方式是：

k从一个常数n一个恒定递增运行，将在O(n^k)
运行从恒定运行到n循环嵌套的循环，你通过一个常数乘以将运行在O(log(n))
如果您有递归（发生在很多分治算法中），您可以使用masters theorem分析复杂性。对于真正的硬递归，有一个Bazzi method.

P.S.与你的问题无关，但整个功能可以用counter代替。

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

来源

2015-12-07 02:27:05

在Python中，你可以做c1 == c2，但需要对其他语言的循环，而这正是笔者试图展现。

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

来源

2015-12-07 02:34:49

看起来作者正试图按照O（1）操作（当试图找出整体运行时复杂度时有意义）阐明算法。

c1 == c2（其中c1和c2是列表）隐藏了一点点复杂性;它实际上更像len(c1) == len(c2) and all(ch1 == ch2 for ch1,ch2 in zip(c1, c2))。他展示了比较中涉及的基本操作。

来源

2015-12-07 02:45:48

了解线性运行时实现的字谜检测

回答

相关问题