这个函数反转字符串中的单词的时间复杂度是多少

Question

我有一个简单的函数reverseWords（），它显示字符串中的单词。输入a 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表示为字符上的循环外，与上述原因相同
• 因为。。。我忘了解释

Answer 1

它是O(N)。我想你不确定的部分是：

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

这里要注意的是，尽管我们确实有嵌套循环（在listA及其每个元素中的字符上），但处理的字符总数仍然只有O(N)。如果k是每个单词中的平均字母数，那么您可以认为时间是N/k（对于外循环）*k（对于内环）=N。在

一个更直接（我认为更好）的分析方法是思考，“我需要为每个角色做什么”？公司名称：

• {cd8>搜索边界^
• 将其复制到split()中的新字符串
• 将新字符串追加到结果列表中（实际上，我们不到每个字符一次，但是big-O的上限是可以的）
• 在listA上推进迭代器（同样，少于一次，每个单词只执行一次）
• 以相反的顺序将其复制到片段中的新字符串中。在
• 将其包含的字符串附加到output（每个单词一次）
• 无论join()做什么（如果你在意，我请你调查一下，或者相信我的话O(total length of all strings)）。在

因此，如果列表的附录、内存分配等都是摊销的O(1)，在CPython中它们是摊销的，那么总的时间复杂度是O(N)，包括{}。在

因为正确的术语很重要，因为它是O(N)，所以它也是{}。在