0%

python常用函数的时间复杂度

作者:18级 潘愽浩

时间复杂度

算法时间复杂度的定义

在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间度量,记作:T(n) = O(f(n))。它表示随问题规模n的增大,算法的执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称为时间复杂度。其中f(n)是问题规模n的某个函数。
(关键就是需要知道执行次数 == 时间)

一般情况下,随着输入规模n的增大,T(n)增长最慢的算法为最优算法。

执行次数T(n)的计算

  1. 用常数1取代运行时间中的所有的加法常数(输入输出指令也全部被取代了)
  1. 只保留最高项
  1. 如果最高项存在且不是1,则去除与这个项相乘的常数(如3*n^2可记为O(n^2))

得到的最终结果就是时间复杂度(可记为大O阶)。

其他算法复杂度表示法

大O表示法:

表示了所有上限中最小的那个上限。

大Ω表示法:

表示了所有下限中最大的那个下限。

f(n) = Ω(g(n))当且仅当g(n) = o(f(n))

大θ表示法:

如果上下限相同,那么就可以用大θ表示

f(n) = Θ(g(n))

当且仅当f(n) = O(g(n))且f(n) = Ω(g(n))

列表和字典常用函数的时间复杂度

sort()列表排序函数,时间复杂度为O(n*logn)

List列表常用操作性能

最常用的是:按索引取值和赋值(v = a[i],a[i] = v)

由于列表的随机访问特性,这两个操作执行时间与列表大小无关,均为O(1)。

另一个是列表增长,可以选择append()和add()”+”

ls.append(v),执行时间是O(1)
ls = ls + [v],执行时间是O(n+k),其中k是被加的列表长度

pop()删除元素函数如果不设置参数(即删除最后一个元素)时时间复杂度为O(1),带参数则为O(n)。

原因是从中部移除元素的话,要把移除元素后面的元素全部向前挪位复制一遍,这个看起来有点笨拙,但这种实现方法能够保证列表按索引取值和赋值的操作很快,达到O(1)。

Dict词典常用操作性能

最常用的取值get和赋值set,其性能为O(1),另一个重要操作contains(in)是判断字典中是否存在某个关键码(key),这个性能也是O(1)

注意:在字典里查找某个关键码为(key in dict)的时间复杂度为O(1),在列表里查找某个元素是否存在(yuan_su in list)的时间复杂度为O(n)。

python更多算法复杂度

Python官方的算法复杂度网站:

http://wiki.python.org/moin/TimeComplexity