代码之家 › 专栏 › 技术社区 › Matthew

发现程序的时间复杂性

complexity-theory time-complexity algorithm

Matthew · 技术社区 · 2 年前

我们如何找到以下程序的时间复杂性?对于以下程序,时间复杂性应为 O(N) 或 O(N*M) 或 O(N*M*M) ?

Take-1: O(N)

扫描输入阵列中的N个元素

Take-2: O(N*M)

N是输入数组中的元素数
M是的列表中最长电子邮件地址的长度 split 和 find

Take-3: O(N*M*M)

N是输入数组中的元素数
第一个M是的列表中直到@为止的最长电子邮件地址的长度 分裂
第二个M是的列表中最长电子邮件地址的长度 发现

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

1 回复 | 直到 2 年前

mandy8055 2 年前

给定程序的时间复杂性为 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

以下是操作对时间复杂性的影响:

循环通过 N 输入数组中的元素: O(N)
在拆分每个电子邮件地址 @ : O(M) ,因为拆分取决于最长电子邮件地址的长度。
正在查找的位置 . : O(M) ,因为找到点还取决于最长电子邮件地址的长度。现在,这里需要注意的一点是 find() 具有最坏情况下的时间复杂性 O(p*q) 哪里 p 是较长字符串的长度, q ,搜索的字符串越短。但既然你提到了你需要找到点( . 所以 q 变为1,对于代码的上下文,它变为 O(M) .

参考文献和进一步阅读:

推荐文章

Matthew · 发现程序的时间复杂性

2 年前

TreasureGhost · 以下函数的时间复杂度是多少

2 年前

Abdullah Kassar · std::upper_bound()是线性的吗?c++

2 年前

user129393192 · 这个问题的最优算法是什么?

2 年前

3366784 · 使用序列初始化字符串的时间复杂度是多少?

2 年前

nehacharya · 这个代码的时间复杂度是O(n^2)还是O(nlogn)?

2 年前

control plane · ruby中链表上size调用的时间复杂性

2 年前

learner · 查找最长的子字符串

2 年前

hackrack · 在javascript中,如何返回时间复杂度为O(n)的相同字母元素?

7 年前

data-oil · 在字符串列表中搜索的高效快捷方法

7 年前