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

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

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

Answer 1

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

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