数据结构和算法基础概念 Data Structures& Algorothms

如果将最终写好运行的程序比作战场，我们码农便是指挥作战的将军，而我们所写的代码便是士兵和武器。 那么数据结构和算法是什么？答曰：兵法！
我们可以不看兵法在战场上肉搏，如此，可能会胜利，可能会失败。即使胜利，可能也会付出巨大的代价。我们写程序亦然：没有看过数据结构和算法，有时面对问题可能会没有任何思路，不知如何下手去解决；
大部分时间可能解决了问题，可是对程序运行的效率和开销没有意识，性能低下；有时会借助别人开发的利器暂时解决了问题，可是遇到性能瓶颈的时候，又不知该如何进行针对性的优化。
如果我们常看兵法，便可做到胸有成竹，有时会事半功倍！同样，如果我们常看数据结构与算法，我们写程序时也能游刃有余、明察秋毫，遇到问题时亦能入木三分、迎刃而解。
故，数据结构和算法是一名程序开发人员的必备基本功，不是一朝一夕就能练成绝世高手的。冰冻三尺非一日之寒，需要我们平时不断的主动去学习积累。

算法的概念

算法是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务。一般地，当算法在处理信息时，会从输入设备或数据的存储地址读取数据，把结果写入输出设备或某个存储地址供以后再调用。
算法是独立存在的一种解决问题的方法和思想。
对于算法而言，实现的语言并不重要，重要的是思想。
算法可以有不同的语言描述实现版本（如C描述、C++描述、Python描述等），我们现在是在用Python语言进行描述实现。

算法的五大特性

输入: 算法具有0个或多个输入
输出: 算法至少有1个或多个输出
有穷性: 算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成
确定性：算法中的每一步都有确定的含义，不会出现二义性
可行性：算法的每一步都是可行的，也就是说每一步都能够执行有限的次数完成

执行时间反应算法效率

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

单靠时间值绝对可信吗？

假设我们将第二次尝试的算法程序运行在一台配置古老性能低下的计算机中，情况会如何？很可能运行的时间并不会比在我们的电脑中运行算法一的214.583347秒快多少。
单纯依靠运行的时间来比较算法的优劣并不一定是客观准确的！
程序的运行离不开计算机环境（包括硬件和操作系统），这些客观原因会影响程序运行的速度并反应在程序的执行时间上。那么如何才能客观的评判一个算法的优劣呢？

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

我们假定计算机执行算法每一个基本操作的时间是固定的一个时间单位，那么有多少个基本操作就代表会花费多少时间单位。算然对于不同的机器环境而言，确切的单位时间是不同的，但是对于算法进行多少个基本操作（即花费多少时间单位）在规模数量级上却是相同的，由此可以忽略机器环境的影响而客观的反应算法的时间效率。
对于算法的时间效率，我们可以用“大O记法”来表示。
“大O记法”：对于单调的整数函数f，如果存在一个整数函数g和实常数c>0，使得对于充分大的n总有f(n)<=c*g(n)，就说函数g是f的一个渐近函数（忽略常数），记为f(n)=O(g(n))。也就是说，在趋向无穷的极限意义下，函数f的增长速度受到函数g的约束，亦即函数f与函数g的特征相似。
时间复杂度：假设存在函数g，使得算法A处理规模为n的问题示例所用时间为T(n)=O(g(n))，则称O(g(n))为算法A的渐近时间复杂度，简称时间复杂度，记为T(n)

如何理解“大O记法”

对于算法进行特别具体的细致分析虽然很好，但在实践中的实际价值有限。对于算法的时间性质和空间性质，最重要的是其数量级和趋势，这些是分析算法效率的主要部分。而计量算法基本操作数量的规模函数中那些常量因子可以忽略不计。例如，可以认为3n2和100n2属于同一个量级，如果两个算法处理同样规模实例的代价分别为这两个函数，就认为它们的效率“差不多”，都为n2级。

最坏时间复杂度

分析算法时，存在几种可能的考虑：

• 算法完成工作最少需要多少基本操作，即最优时间复杂度
• 算法完成工作最多需要多少基本操作，即最坏时间复杂度
• 算法完成工作平均需要多少基本操作，即平均时间复杂度
• 对于最优时间复杂度，其价值不大，因为它没有提供什么有用信息，其反映的只是最乐观最理想的情况，没有参考价值。
• 对于最坏时间复杂度，提供了一种保证，表明算法在此种程度的基本操作中一定能完成工作。
• 对于平均时间复杂度，是对算法的一个全面评价，因此它完整全面的反映了这个算法的性质。但另一方面，这种衡量并没有保证，不是每个计算都能在这个基本操作内完成。而且，对于平均情况的计算，也会因为应用算法的实例分布可能并不均匀而难以计算。
• 因此，我们主要关注算法的最坏情况，亦即最坏时间复杂度。

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

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

常见时间复杂度

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

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

所消耗的时间从小到大

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

Python内置类型性能分析

• 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类型的秒数。

list的操作测试

def 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))

from timeit import Timer

t1 = Timer("test1()", "from __main__ import test1")
print("concat ",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")

# ('concat ', 1.7890608310699463, 'seconds')
# ('append ', 0.13796091079711914, 'seconds')
# ('comprehension ', 0.05671119689941406, 'seconds')
# ('list range ', 0.014147043228149414, 'seconds')

pop操作测试

x = range(2000000)
pop_zero = Timer("x.pop(0)","from __main__ import x")
print("pop_zero ",pop_zero.timeit(number=1000), "seconds")
x = range(2000000)
pop_end = Timer("x.pop()","from __main__ import x")
print("pop_end ",pop_end.timeit(number=1000), "seconds")

# ('pop_zero ', 1.9101738929748535, 'seconds')
# ('pop_end ', 0.00023603439331054688, 'seconds')

• 测试pop操作：从结果可以看出，pop最后一个元素的效率远远高于pop第一个元素

python list内置操作的时间复杂度

Operation	Big-O Efficiency
indexx	O(1)
index assignment	O(1)
append	O(1)
pop()	O(1)
pop(i)	O(n)
insert(i,item)	O(n)
del operator	O(n)
iteration	O(n)
contains (in)	O(n)
get slice [x:y]	O(k)
del slice	O(n)
set slice	O(n+k)
reverse	O(n)
concatenate	O(k)
sort	O(nlogn)
multiply	O(nk)

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

Operation	Big-O Efficiency
copy	O(n)
get_item	O(1)
set_item	O(1)
delete_item	O(1)
contains(in)	O(1)
Iteration	O(n)

数据结构

我们如何用Python中的类型来保存一个班的学生信息？ 如果想要快速的通过学生姓名获取其信息呢？
实际上当我们在思考这个问题的时候，我们已经用到了数据结构。列表和字典都可以存储一个班的学生信息，但是想要在列表中获取一名同学的信息时，就要遍历这个列表，其时间复杂度为O(n)，而使用字典存储时，可将学生姓名作为字典的键，学生信息作为值，进而查询时不需要遍历便可快速获取到学生信息，其时间复杂度为O(1)。
我们为了解决问题，需要将数据保存下来，然后根据数据的存储方式来设计算法实现进行处理，那么数据的存储方式不同就会导致需要不同的算法进行处理。我们希望算法解决问题的效率越快越好，于是我们就需要考虑数据究竟如何保存的问题，这就是数据结构。
在上面的问题中我们可以选择Python中的列表或字典来存储学生信息。列表和字典就是Python内建帮我们封装好的两种数据结构。

概念

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

算法与数据结构的区别

数据结构只是静态的描述了数据元素之间的关系。
高效的程序需要在数据结构的基础上设计和选择算法。
程序 = 数据结构 + 算法
总结：算法是为了解决实际问题而设计的，数据结构是算法需要处理的问题载体

抽象数据类型(Abstract Data Type)

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

• 插入
• 删除
• 修改
• 查找
• 排序

附表-数据结构和算法专业术语中英文对照

English	中文
Abstract Data Type	抽象数据类型	Hashtable	哈希表，映射
ADT	抽象数据类型	Heap	堆
Algorithm	算法	Index	索引
Array	数组	“Insertion Sort”	插入排序
ArrayList	动态数组	Interface	接口
Average Case	平均情况	Iteration	迭代
Balance Tree	平衡树	Linear	线性级别
BAT	百度，阿里，腾讯	“Linked List”	链表
Best Case	最好情况	Logarithmic	对数级别
BFS	广度优先搜索	Lookup	查找
Big O 大 O	符号	“Lower Bounds”	下限
Binary Search	二分搜索	“Master Theorem”	主项定理
Binary Search Tree	二叉搜索树	Math	数学
Binary Tree	二叉树	Memorization	记忆化
Bit Manipulation	二进制处理	“Merge Sort”	归并排序
Bit Operation	微操作	Module	模块
Bottom-up	从下往上	N-Log-N	线性对数级别
Boundary Check	边界检查	“Non-Deterministic Polynomial”	非确定多项式问题
Breath First Search	广度优先搜索	“Object Oriented”	面向对象
Brute Force	暴力破解	“Open Addressing”	开发寻址
Bubble Sort	冒泡排序	Partition	分组
Collision	冲突	Pivot	枢纽
Complexity	复杂度	Polynomial	多项式
Constant	常数级别	Quadratic	平方级别
Continuous	连续的	Queue	队列
Count Sort	计数排序	“Quick Sort”	快速排序
Cubic	立方级别	Recursion	递归
Customized Hash Object	自定义哈希类	“Red Black Tree”	红黑树
Data Engineer	数据工程师	Rehash	重新配置
Data Scientist	数据科学家	“Rolling Hash”	滚动哈希
Data Structure	数据结构	“Running Time”	运行时间
Depth First Search	深度优先搜索	Search	搜索
Deque	双向队列	“Selection Sort”	选择排序
DFS	深度优先搜索	“Separate Chain”	独立链表
Dijkstra Algorithm	迪杰斯特拉算法	“Shell Sort”	希尔排序
Divide	拆分	“Shortest Path”	最短路径
Divide and Conquer	分治算法	“Sliding Windows”	滑动窗口算法
Double Hash	双重哈希	“Software Engineer”	软件工程师
Doubly Linked List	双向链表	Sort	排序
DP	动态规划	“Space Complexity”	空间复杂度
Dynamic Array	动态数组	Stack	栈
Dynamic Programming	动态规划	Streaming	流
Efficiency	效率	String	字符串
Exponential	指数级别	“Time Complexity”	时间复杂度
FLAG	脸书，领英，亚马逊，谷歌	Top-Down	从上往下
Graph	图论	“Topology Sort”	拓扑排序
Greedy Algorithm	贪婪算法	Tree	树
Hash Function	哈希函数	“Two Pointers”	双指针算法
Hashcode	哈希码	Union Find	并查集
Worst Case	最差情况	“Upper Bounds”	上限