Github上复旦小姐姐原创「数据结构和算法系列」( 二 ) _Github

第一个for循环为常数循环，复杂度为O(1)，第二个for为单层循环，为O(n)，第三个for循环为双层嵌套循环，时间复杂度为O(n^2) 。如T(n) = max(O(1),O(n),O(n^2)) = O(n^2) 。分析算法时，存在几种可能：※最优时间复杂度：最少需要多少基本操作li = [1,2,3,4,5]列表有序，则常数时间，O(1) 。※平均时间复杂度：平均需要多少基本操作※最坏时间复杂度：最多需要多少基本操作列表无序时，时间复杂度与元素个数正相关，即O(n) 。最优时间复杂度和平均时间复杂度价值不大，未提供太多有用的信息，因此主要关注算法的最坏情况，亦即最坏时间复杂度。
四、常见的时间复杂度O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)、O(2^n)
列表比较：执行次数实例复杂度非正式术语10O(1)常数阶3n+2O(n)线性阶2n^2^+3n+1O(n^2^)平方阶2log~2~n+10O(log~2~n)对数阶2nlog~2~n+2n+3O(nlog~2~n)nlog~2~n阶2^n^O(2^n^)指数阶
绘图说明：

文章插图

各种时间复杂度图形比较
再分析：
def cal(n): for i in range(n): for j in range(i): print(i,j)要计算1+2+3+…+(n-1)=n*(n-1)/2，所以也为O(n^2) 。
五、Python内置类型性能分析timeit模块用来测试一段代码的执行时间：三个参数：stmt, setup, timer即class timeit.Timer(stmt='',setup='',timer='')Timer:测试小段代码执行时间的类;stmt:要测试的代码语句;setup:运行代码时需要的设置;timer:定时器参数,与平台有关。

#分析列表添加的执行效率from timeit import Timerdef test1():    l = []    for i in range(1000):        l = l + [i]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))def test5():    l = []    for i in range(1000):        #从头添加        l.insert(0,i)#函数要加引号t1 = Timer('test1()','from __main__ import test1')print('add',t1.timeit(number=1000))t2 = Timer('test2()','from __main__ import test2')print('append',t2.timeit(number=1000))t3 = Timer('test3()','from __main__ import test3')print('list derivation',t3.timeit(number=1000))t4 = Timer('test4()','from __main__ import test4')print('list range',t4.timeit(number=1000))t5 = Timer('test5()','from __main__ import test5')print('insert',t5.timeit(number=1000))

打印

add 1.223421629append 0.06038822500000007list derivation 0.030709197000000188list range 0.012542454999999952insert 0.2713445080000001

易知，第一种方式最慢，insert()方法稍快，append()更快，其他的也较快。
六、数据结构的引入数据存储方式的不同，会导致需要不同的算法进行处理,其执行效率也会不同。如在用Python中的类型来存储一个班的学生信息时,可以考虑通过列表和字典两种方式.在通过学生姓名获取其信息时,如通过列表,则要遍历这个列表,其时间复杂度为O(n)(假设学生规模为n)而通过字典存储时,可以将学生姓名作为字典的键,学生信息作为值,进行查询时不需要遍历即可快速获取到学生信息,时间复杂度为O(1).这说明数据存储方式的不同的确会导致需要的算法不同,用算法解决问题的效率也会不同。数据是一个抽象的概念,将其分类后得到程序设计语言的基本类型，如常见的int、float、char等。数据元素之间不是独立的，存在特定的关系，这些关系便是结构。定义：数据结构指数据对象中数据元素之间的关系，即数据组织的方式。Python中，数据结构分为：内置数据结构：Python已经实现，不需要我们再去定义，如列表、元组、字典等；扩展数据结构：Python并未定义，需要我们自己去定义实现这些数据的组织方式，如栈、队列等。程序 = 数据结构 + 算法总结：算法是为了解决实际问题而设计的，数据结构是算法需要处理问题的载体。抽象数据类型（ADT）：指一个数据类型以及定义在此数据模型上的一组操作，即把数据类型和数据类型上的运算捆绑在一起，进行封装。引入抽象数据类型的目的是把数据类型的表示和数据类型上运算的实现与这些数据类型和运算在程序中的引用隔开，使它们相互独立。