python数据结构

文章目录

算法效率衡量算法效率衡量标准 常见的时间复杂度计算时间复杂度的大小对比时间复杂度的基本规则 Python内置类型性能分析timeit模块list内置操作的时间复杂度list内置操作的时间复杂度 数据结构算法与数据结构的区别抽象数据类型(Abstract Data Type)

算法效率衡量

如果 a+b+c=300，且 aa+bb=c*c（a,b,c 为自然数），如何求出所有a、b、c可能的组合?

// An highlighted block '''枚举法''' #三层循环 import time start_time1 = time.time() for a in range(0, 301): for b in range(0, 301): for c in range(0, 301): if a**2 + b**2 == c**2 and a+b+c == 300: print("a, b, c: %d, %d, %d" % (a, b, c)) end_time1 = time.time() print("elapsed: %f" % (end_time1 - start_time1)) print("****************************") '''代码改进''' #两层循环 start_time2 = time.time() for a in range(0, 301): for b in range(0, 301): c = 300 - a - b #将c的范围降维300-a-b if a**2 + b**2 == c**2: print("a, b, c: %d, %d, %d" % (a, b, c)) end_time2 = time.time() print("elapsed: %f" % (end_time2 - start_time2))

从两种算法中可以得知第一种算法的计算时间明显长于第二种算法。

算法效率衡量标准

算法效率衡量标准是时间复杂度，因为基本运算数量大致相同。 例如前边的两个算法： 第一种：三种循环，每次循环300次，判断语句执行两次，判断结果有两种(print，else)，其中print是1次，else是0次。 T1=300300300*(2+(max(0,1)) 第二种：两种循环，每次循环300次，顺序语句一次，判断语句执行。 T2=300300(1+max(0,1)) 说明第二种的算法效率低。

常见的时间复杂度计算

时间复杂度的大小对比

时间复杂度有 最优时间复杂度、最坏时间复杂度、平均时间复杂度，但是一般遵循最坏时间复杂度。

时间复杂度的基本规则

常数：O(1) n次项：只保留最高次项 顺序结构：加法 循环结构：乘法 判断结构：根据分支，选择分支步骤最多的

Python内置类型性能分析

timeit模块

Timer是测量小段代码执行速度的类。 stmt参数是要测试的代码语句（statment）； setup参数是运行代码时需要的设置； timer参数是一个定时器函数，与平台有关。

timeit.Timer.timeit(number=1000000) Timer类中测试语句执行速度的对象方法。number参数是测试代码时的测试次数，默认为1000000次。方法返回执行代码的平均耗时，一个float类型的秒数。

// An highlighted block from timeit import Timer '''加法+''' def test1(): l = [] for i in range(1000): l = l + [i] '''append''' def test2(): l = [] for i in range(1000): l.append(i) def test3(): l = [i for i in range(1000)] def test4(): l = list(range(1000)) '''extend''' def test5(): l = [] for i in range(1000): l.extend([i]) '''insert''' def test6(): l = [] for i in range(1000): l.insert(0,i) t1 = Timer("test1()", "from __main__ import test1") print("+:",t1.timeit(number=1000), "seconds") t2 = Timer("test2()", "from __main__ import test2") print("append: ",t2.timeit(number=1000), "seconds") t3 = Timer("test3()", "from __main__ import test3") print("comprehension: ",t3.timeit(number=1000), "seconds") t4 = Timer("test4()", "from __main__ import test4") print("list range: ",t4.timeit(number=1000), "seconds") t5 = Timer("test5()", "from __main__ import test5") print("extend: ",t5.timeit(number=1000), "seconds") t6 = Timer("test6()", "from __main__ import test6")

从六种算法中可以看出，“+”的运算量最大， insert(0,i) 因为要从首位置对元素进行增加操作，因此计算量也很大。

list内置操作的时间复杂度

list内置操作的时间复杂度

数据结构

数据是一个抽象的概念，将其进行分类后得到程序设计语言中的基本类型。如：int，float，char等。数据元素之间不是独立的，存在特定的关系，这些关系便是结构。数据结构指数据对象中数据元素之间的关系。 Python提供了很多现成的数据结构类型，这些系统定义好的，叫做Python的内置数据结构，比如列表、元组、字典。而有些数据组织方式，Python系统里面没有直接定义，需要自己去定义实现这些数据的组织方式，这些数据组织方式称之为Python的扩展数据结构，比如栈，队列等。

算法与数据结构的区别

数据结构只是静态的描述了数据元素之间的关系。高效的程序需要在数据结构的基础上设计和选择算法。 程序 = 数据结构 + 算法

抽象数据类型(Abstract Data Type)

抽象数据类型(ADT)的含义是指一个数学模型以及定义在此数学模型上的一组操作。即把数据类型和数据类型上的运算捆在一起，进行封装。引入抽象数据类型的目的是把数据类型的表示和数据类型上运算的实现与这些数据类型和运算在程序中的引用隔开，使它们相互独立。 最常用的数据运算有五种：插入、删除、修改、查找、排序。