python - 这个函数的大 O 是什么，可以反转字符串中的单词

Question

我有一个简单的函数 reverseWords()，它可以反转字符串中的单词。例如。 S = "this is a string"的输入给出 "siht si a gnirts"的输出

我想知道这个函数的大 O 是什么。是 O(N)、O(N^2) 还是 O(N* M)？

def reverseWords(S):
    # code in Python 2.7
    listA = S.split()
    output = []
    for element in listA:
        output.append(element[::-1])

    return (" ".join(output))

是 O(N)、O(N^2) 还是 O(N* M)？

• O(N^2) 因为我们有一个嵌套循环，例如。传递一次输入，外循环，然后将每个字符反转为内循环
• O(N*M) 同上，除了 M 被表示为字符循环
• O(N) 因为...我忘了解释

Answer 1

它是O(N)。我假设您不确定的部分是:

for element in listA:
    output.append(element[::-1])

这里要注意的是，虽然我们确实有嵌套循环(在 listA 和它的每个元素中的字符上)，处理的字符总数仍然只有 O (N)。如果 k 是每个单词的平均字母数，那么你可以将时间视为 N/k(对于外循环)* k(对于内部循环)= N。

一种更直接(我会说更好)的分析方法是思考“我需要为每个角色做什么”？:

• 扫描它以寻找 split() 中的单词边界
• 将其复制到 split() 中的新字符串
• 将新字符串附加到结果列表(实际上，我们对每个字符执行此操作的次数少于一次，但对于 big-O 而言，上限没问题)
• 在 listA 上推进迭代器(同样，少于一次，每个单词仅一次)
• 以相反的顺序将其复制到切片中的新字符串中。
• 将其包含的字符串附加到output(每个单词一次)
• 无论 join() 做什么(如果您关心，我邀请您调查，或者相信我的话，它是 O(所有字符串的总长度))。

因此，假设列表追加、内存分配等等都是分摊的 O(1)，在 CPython 中就是这样，那么总体时间复杂度是 O(N ) 包括 join()。

由于正确的术语很重要，因为它是 O(N) 因此它也是 O(N^2)。