Python数据结构与算法

33次阅读
没有评论

共计 1250 个字符,预计需要花费 4 分钟才能阅读完成。

算法复杂度分为时间复杂度和空间复杂度。时间复杂度 是指程序要执行的次数,而非执行时间;而 空间复杂度 是指算法执行过程中大概所占用的最大内存空间。计算机资源最重要的是时间和空间 (即寄存器) 资源,因此复杂度分为时间和空间复杂度。

大 O 表示法

大 O 时间复杂度表示法:T(n)=O(f(n))。大 O 时间复杂度实际上并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,所以,也叫作渐进时间复杂度(asymptotic time complexity),简称时间复杂度。

常见的大 O 数量级函数:

f(n) 名称
1 常数
log(n) 对数
n 线性
n*log(n) 对数线性
平方
立方
2ⁿ 指数

Python 数据结构与算法

列表常用操作性能

按索引取值和赋值(v=a[i],a[i]=v),由于列表的随机访问特性,这两个操作执行时间与列表大小无关,均为 O(1)。

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

4 种生成 n 个整数列表的方法:

from timeit import Timer

def t1():
    lst = []
    for i in range(1000):
        lst = lst + [i]

def t2():
    lst = []
    for i in range(1000):
        lst.append(i)

def t3():
    lst = [i for i in range(1000)]

def t4():
    lst = list(range(1000))

time1 = Timer("t1()", "from __main__ import t1")
print("concat:\t\t{} seconds".format(time1.timeit(1000)))

time2 = Timer("t2()", "from __main__ import t2")
print("append:\t\t{} seconds".format(time2.timeit(1000)))

time3 = Timer("t3()", "from __main__ import t3")
print("comprehension:\t{} seconds".format(time3.timeit(1000)))

time4 = Timer("t4()", "from __main__ import t4")
print("list range:\t{} seconds".format(time4.timeit(1000)))

可以看到,4 种方法运行时间差别挺大的,列表连接(+)最慢,中间的是 append 和列表推导式,List range 最快。

字典常用操作性能

与列表不同,字典是根据键值(key)找到数据项,而列表是根据索引(index)。最常用的取值和赋值,其性能均为 O(1)。另一个重要操作 contains(in)是判断字典中是否存在某个键值(key),这个性能也是 O(1)。

更多 Python 数据类型操作复杂度可参考官方文档:https://wiki.python.org/moin/TimeComplexity

正文完
post-qrcode
 0
三毛
版权声明:本站原创文章,由 三毛 于2023-09-21发表,共计1250字。
转载说明:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(没有评论)