如何判断一段Python邮件处理代码的时间复杂度？

代码示例 #

input_mails = ["abc@gmail.com","xyz@gmail.com"] 
for email in input_mails: 
    first_part, second_part = email.split("@") 
    position = email.find(".")
    print(first_part)

针对这段代码，我们需要判断它的时间复杂度到底属于O(N)、O(NM)还是O(NM*M)，目前有三种不同的分析思路：

分析一：O(N) #

• 仅统计遍历输入数组中N个元素的次数，忽略字符串操作的时间开销

分析二：O(N*M) #

• N为输入数组中的元素数量
• M为列表中最长邮箱地址的长度，对应split("@")和find(".")操作的时间开销

分析三：O(NMM) #

• N为输入数组中的元素数量
• 第一个M为列表中@符号前最长邮箱地址的长度，对应split("@")操作
• 第二个M为列表中最长邮箱地址的长度，对应find(".")操作

正确结论：时间复杂度为O(N*M) #

理由如下：

1. 外层循环遍历N个邮箱，时间开销为O(N)
2. 对于每个邮箱字符串：
   • split("@")需要遍历字符串直到找到@，最坏情况下需遍历整个字符串（长度M），时间复杂度O(M)
   • find(".")同理，最坏情况遍历整个字符串，时间复杂度O(M)
   • 单次循环内的总时间为O(M)+O(M)=O(M)
3. 整体时间复杂度为N * O(M) = O(N*M)

分析一的疏漏在于忽略了字符串操作的时间成本，这类操作并非O(1)；分析三错误地将split的时间单独拆分，且错误地将两个O(M)操作相乘，实际上二者相加后仍为O(M)，因此整体不会达到O(NMM)的复杂度。

内容的提问来源于stack exchange，提问作者Matthew