2.3.5 复杂度

本节目标：

• 了解复杂度的概念

• 以后写代码的时候复杂度心里要有数

运行以下代码，

a = []
b = 1
for i in range(1000000):
    b = (b<<8)+b+253&0xffffffff
    a.append(b)

a.sort()

先建立了一个随机生成的长度为1000000的list，然后对它排序。

可以明显感觉到，排序的过程中，机子卡了一下。（没卡的在1000000后面再加两个0）

这个例子说明，sort很慢。

程序运行的速度通常是很重要的，于是有“时间复杂度”来衡量这个指标。

Learning By Reading 难度：★★★ 重要性：★★

• 时间复杂度

Learning By Reading 难度：★ 重要性：★★★★

• Python基本数据类型的时间复杂度

同样，计算机内存有限，也有衡量空间的指标叫“空间复杂度”，概念与“时间复杂度”类似。

Learning By Doing 难度：★ 重要性：★★★★

• 写代码验证阅读材料中的时间复杂度

• 试试自己的电脑能开多大的list

• 和同组的小伙伴们炫耀炫耀自己电脑的性能

Tasks For Tutors

• 复杂度的概念是忽略系数的，但系数在实际当中有时候也很重要，这通常需要具体问题具体分析。

  向学员们介绍一下在你的学习、工作中遇到的需要优化时间或空间开销的问题，以及这时候应该去考虑复杂度还是系数。

• 一种编程语言需要转换成机器语言才能在电脑中运行，同样的功能，不同的编程语言转换的结果很少会一样。

  而且，例如“对象”这种比较复杂的概念在转换成相对简陋的机器语言时也需要很多很多额外的工作，

  不同的语言在处理例如“对象”概念的时候也会有不同的操作。

  这些种种差异最终不同语言在运行效率上会有比较显著的差异。

  Python的运行速度如何？向学员们介绍一下你了解的编程语言在效率方面的表现。