求程序的时间复杂度

Question

我们如何找到以下程序的时间复杂度？对于下面的程序，时间复杂度应该是

O(N)

还是

O(N*M)

还是

O(N*M*M)

？

采取1：

O(N)

• 扫描输入数组中的 N 个元素

第二次：

O(N*M)

• N 是输入数组中的元素数量
• M 是

  split

  和

  find

列表中最长电子邮件地址的长度

第三步：

O(N*M*M)

• N 是输入数组中的元素数量
• 第一个 M 是

  split

列表中直到@为止的最长电子邮件地址的长度
• 第二个 M 是

  find

列表中最长电子邮件地址的长度

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

Answer 1

给定程序的时间复杂度为

N*2M

~

O(N * M)

其中：

N: number of elements in the input array (input_mails)
M: length of the longest email address in the list

以下是操作如何影响时间复杂度：

1. 循环输入数组中的

   N

   元素：

   O(N)

2. 在“@”处拆分每个电子邮件地址：

   O(M)

   ，因为拆分取决于最长电子邮件地址的长度。
3. 查找“.”的位置：

   O(M)

   ，因为查找点还取决于最长电子邮件地址的长度。