一、概念:

1. 数据结构预算法的作用

1.没有看过数据结构和算法，有时面对问题可能会没有任何思路，不知如何下手去解决；2.大部分时间可能解决了问题，可是对程序运行的效率和开销没有意识，性能低下；3.有时会借助别人开发的利器暂时解决了问题，可是遇到性能瓶颈的时候，又不知该如何进行针对性的优化。

计算机界著名公式，由瑞士计算机科学家尼克劳斯·威茨（Niklaus Wirth）提出，也因此获得图灵奖。 程序 = 数据结构 + 算法

2.算法效率衡量:

2.1 执行时间反应算法效率

对于同一问题，给出了两种解决算法，在两种算法的实现中，对程序执行的时间进行了测算，发现两段程序执行的时间相差悬殊（214.583347秒相比于0.182897秒），由此可以得出结论：实现算法程序的执行时间可以反应出算法的效率，即算法的优劣。

2.2 时间频度

一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

2.2.1 时间复杂度与“大O记法”

上面提到的时间频度T(n)中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时想知道它变化时呈现什么规律，为此引入时间复杂度的概念。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，如果存在一个整数函数g和实常数c>0，使得对于充分大的n总有T(n)<=c*g(n)，就说函数g是T(n)函数的一个渐近函数（忽略常数），记为T(n)=O(g(n))，它称为算法的渐进时间复杂度，简称时间复杂度。这种用O( )来体现算法时间复杂度的记法，称之为大O表示法。

大O表示法实际就是去掉T(n)函数的最高阶项系数、低阶项和常数项，只保留最高阶项。如T(n)函数为5n3 + 3n + 5，使用大O表示法则时间复杂度为O(n3)。

2.2.2 如何理解“大O记法”

对于算法的效率衡量，最重要的是其数量级和趋势，这些是分析算法效率的主要部分。而计量算法基本操作数量的规模函数中那些常量因子可以忽略不计。例如，可以认为3n2和100n2属于同一个量级，如果两个算法处理同样规模实例的代价分别为这两个函数，就认为它们的效率“差不多”，都为n2级。

2.2.3 时间复杂度的分类

时间复杂度根据操作的多少分为如下三种：

最优时间复杂度:算法完成工作最少需要多少基本操作最坏时间复杂度:算法完成工作最多需要多少基本操作平均时间复杂度:算法完成工作平均需要多少基本操作

对于最优时间复杂度，其价值不大，因为它没有提供什么有用信息，其反映的只是最乐观最理想的情况，没有参考价值。

对于最坏时间复杂度，提供了一种保证，表明算法在此种程度的基本操作中一定能完成工作。

对于平均时间复杂度，是对算法的一个全面评价，因此它完整全面的反映了这个算法的性质。但另一方面，这种衡量并没有保证，不是每个计算都能在这个基本操作内完成。而且，对于平均情况的计算，也会因为应用算法的实例分布可能并不均匀而难以计算。

因此，主要关注算法的最坏情况，亦即最坏时间复杂度。

2.2.4 时间复杂度的几条基本计算规则

基本操作，即只有常数项，认为其时间复杂度为O(1),顺序结构，时间复杂度按加法进行计算循环结构，时间复杂度按乘法进行计算分支结构，时间复杂度取最大值判断一个算法的效率时，往往只需要关注操作数量的最高次项，其它次要项和常数项可以忽略在没有特殊说明时，所分析的算法的时间复杂度都是指最坏时间复杂度

2.3 空间复杂度

空间复杂度的概念 类似于时间复杂度的讨论，一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。**空间复杂度(SpaceComplexity)是对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度和时间复杂度的关系** 对于一个算法，其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间；反之，当追求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。大部分时间在完成一个程序时采用空间换时间的策略算法的时间复杂度和空间复杂度合称为算法的复杂度。

3. 常见时间复杂度

3.1 常见的时间复杂度:

执行次数函数举例阶非正式术语12O(1)常数阶2n+3O(n)线性阶3n2+2n+1O(n2)平方阶5log2n+20O(logn)对数阶2n+3nlog2n+19O(nlogn)nlogn阶6n3+2n2+3n+4O(n3)立方阶2nO(2n)指数阶

注意，经常将log2n（以2为底的对数）简写成logn

3.2 常见时间复杂度之间的关系

所消耗的时间从小到大

O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

4.Python内置类型性能分析 --timeit模块

4.1 timeit模块

timeit模块可以用来测试一小段Python代码的执行速度。 class timeit.Timer(stmt=‘pass’, setup=‘pass’, timer=)

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

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

4.2 list的操作测试

def t1(): l = [] for i in range(1000): l = l + [i] def t2(): l = [] for i in range(1000): l.append(i) def t3(): l = [i for i in range(1000)] def t4(): l = list(range(1000)) from timeit import Timer timer1 = Timer("t1()", "from __main__ import t1") print("concat ",timer1.timeit(number=1000), "seconds") timer2 = Timer("t2()", "from __main__ import t2") print("append ",timer2.timeit(number=1000), "seconds") timer3 = Timer("t3()", "from __main__ import t3") print("comprehension ",timer3.timeit(number=1000), "seconds") timer4 = Timer("t4()", "from __main__ import t4") print("list range ",timer4.timeit(number=1000), "seconds") # ('concat ', 1.7890608310699463, 'seconds') # ('append ', 0.13796091079711914, 'seconds') # ('comprehension ', 0.05671119689941406, 'seconds') # ('list range ', 0.014147043228149414, 'seconds')

insert与append比较

def t2(): li = [] for i in range(10000): li.append(i) def t5(): li = [] for i in range(10000): li.insert(0, i) timer2 = Timer('t2()', 'from __main__ import t2') print("append:", timer2.timeit(number=1000)) timer5 = Timer('t5()', 'from __main__ import t5') print("insert:", timer5.timeit(number=1000)) # append: 0.9202240769991477 # insert: 21.039387496999552

从结果可以看出，append从尾端添加元素效率远远高于insert从顶端添加元素

4.3 list内置操作的时间复杂度:

operationBig-O Efficiencyindex x[]O(1)index assignmentO(1)appendO(1)pop()O(1)pop(i)O(n)insert(i, item)O(n)del operatorO(n)iterationO(n)contains(in)O(n)get slice[x:y]O(k)del sliceO(n)set sliceO(n+k)reverseO(n)concatenateO(k)sortO(nlogn)multiplyO(nk)

4.4 dict内置操作的时间复杂度

OperationBig-O EfficiencycopyO(n)get itemO(1)set itemO(1)delete itemO(1)contains(in)O(1)iterationO(n)

5数据结构:

5.1 概念:

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

为了解决问题，需要将数据保存下来，然后根据数据的存储方式来设计算法实现进行处理，那么数据的存储方式不同就会导致需要不同的算法进行处理。希望算法解决问题的效率越快越好，于是就需要考虑数据究竟如何保存的问题，这就是数据结构。