这段用于反转字符串单词的代码的时间复杂度是多少？

Question

input_string= "This is a string"
output=''
words=input_string.split(" ")
print(words)
for word in words:
    ts=''
    for l in range(len(word)-1,-1,-1):
        ts+=word[l]
    output+=ts + ' '

print(output)

我认为复杂度为 o(n^2)，但我也对 o(nm) 的复杂度感到困惑，因为对于每个单词，我然后遍历它的字母，这些字母本质上是长度为 m

的子串

如何确定正确的复杂度？

Answer 1

尝试检测流程中的循环（隐式和显式）及其相对基数。

input_string.split(' ') 遍历字符一次，所以 O(n)
for l in range(len(word)...嵌套在for word in words中，每个字符只处理一次，所以也是O(n)
output+=ts + ' ' 每个单词执行一次，但嵌套循环不包含空格，因此嵌套循环的操作总数仍将小于或等于 n

简而言之，复杂度为O(n)。

但是，如有疑问，请计时！您可以尝试各种字符串长度并（使用 timeit）确定进展是否确实是线性的（即时间与字符串长度成比例）

这段用于反转字符串单词的代码的时间复杂度是多少？

What is the time complexity of this code for reversing words of a string?

python

time-complexity