这个函数的大 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.

更直接（我会说更好）的分析方法是思考，"what do I need to do for each character"?:

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

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

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

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

What is the Big-O of this function that reverses words in a string

python

big-o

time-complexity