字符串单词反转代码的时间复杂度是多少？如何判定正确复杂度？

你提供的实现代码如下：

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)，其中N为输入字符串的总字符数：

• split操作会完整遍历一次输入字符串，开销为O(N)
• 双层循环的总执行次数等于所有单词的长度之和，和N呈线性关系。你疑惑的O(nm)如果是指n为单词数量、m为单个单词的平均长度，那么n*m的结果就是所有单词的总长度，和O(N)完全等价，不属于平方级复杂度。只有当你错误将输入规模定义为单词数量，且默认每个单词长度等于单词数量时，才会得到平方级的结果，这不符合字符串处理类算法的常规输入规模统计规则（常规以总字符数作为输入规模）。

考虑Python字符串不可变的拼接开销 #

Python中字符串是不可变对象，每次执行ts += word[l]都会生成新的字符串，需要复制当前ts的所有字符再加新字符。对长度为m的单个单词，这部分的开销为1+2+...+m = O(m²)。
这种场景下总时间复杂度为 O(N·M)，其中M为单词的平均长度。极端情况下如果整个输入只有一个单词，那么M=N，总复杂度就是O(N²)，和你最初的判断一致。

复杂度确定方法 #

先明确两个核心变量即可：

1. 你定义的输入规模是什么（字符串处理场景默认是总字符数）
2. 是否要考虑编程语言本身的特性带来的额外操作开销

内容的提问来源于stack exchange，提问作者Mr. Mak