算法定义

算法（Algorithm）是对特定问题求解步骤的一种描述。

衡量算法的指标

1.时间复杂度：执行这个算法需要消耗多少时间；（大O表示法）

2.空间复杂度：这个算法需要占用多少内存。

算法在时间的高效性和空间的高效性之间通常时矛盾的，所以一般需要一个平衡点。通常我们假设程序运行在足够大的空间中，所以研究更多的是算法的时间复杂度。

常见的时间复杂度有：

常数阶O(1)；

对数阶O(Log2n) à二分查找

线性阶O(n) à普通查找

线性对数阶O(n Log2n) à快速排序

平方阶O(n2) à选择排序

立方阶O(n3);

k次方阶O(nk) ；

O(n!) ;–à旅行商问题

指数阶O(2n)

平均时间复杂度和最坏时间复杂度

一般讨论的是最坏时间复杂度:表示了算法在任何输入情况下运行时间的界限，运行时间不会有比最坏的时间更长的时间。

查找

简单查找

O(n)

二分法查找

前提：所查找的列表是有序列表。

每次查找都会排除一般的值。

O(log2n) 100个元素最多查找7次 log2100 à7 ；40亿个元素，最多查找32次

N表示所查找的元素个数。

元素越多二分法相对于简单查找的优势越明显。

不同时间复杂度的时间对比：

二分法实现的代码：（python）

数组与链表

数组

特点：元素在内存中是相连的，需要连续的内存空间。(每个元素有指定索引)

优势：查找元素，随机读取元素时，效率高，因为每个元素有指定的索引。

链表

特点：元素可以存储在内存的任何地方，链表中每个元素都存储了下一个元素的地址。

优势：插入元素

数组支持随机访问，而链表必须顺序访问，因为每个元素的地址都存储在上一个元素中。

混合数据：链表数组

特点：查找时，速度比数组慢，但比链表快；而插入时，速度比数组快，与链表相当

排序

选择排序

每次找出数组中最小的元素，查找n次. àO(n)

代码：

快速排序—分治思想

每次从列表取出一个基准值，然后根据基准值将列表分为两个部分，比基准值到的部分List1和比基准值小的部分list2；然后对个list1与list2分别执行同样的操作。

每次取列表第一个值当基准值：

每次随机取列表中的值当基准值：（一般随机取比较好）

递归

每个递归函数都包含基线条件(base case)和递归条件(recursive case)。

基线条件：递归结束的条件；

递归条件：运行递归的条件，

栈

先进后出

有入栈和出栈操作；

所有函数的调用都进入调用栈。

缺点：如果栈层数很多，就会占用大量的存储空间。

散列表

散列函数

将输入映射到数字。

特征：

1，散列函数总是将同样的输入映射到相同的索引；

2，散列函数将不同的输入映射到不同的索引；（尽可能映射到不同索引，有可能不同输入对应同一索引（称为冲突），最理想的情况时散列函数将键均匀地映射到散列表的不同位置。）

散列表（hash table）

散列表= 散列函数 + 数组

Python中提供的散列表为字典。Dict1= {} 或者dict()；创建空字典。

散列表适用的情况：

1.模拟映射关系；

2.防止重复；

3.缓存/记住数据，以免服务器再通过处理来生成他们。

散列表的查找、插入和删除速度都很快。

避免冲突的方式：

1.较低的填装因子；（填装因子=散列表包含的元素个数/位置总数）；

2.良好的散列函数。

填装因子越低，发生冲突的可能性越小，散列表性能越高。

一个不错的经验规律：一旦填装因子大于0.7，就调整散列表的长度。（通常将长度增加一倍）

缓存

工作原理：将常用的数据存储在内存中。

缓存是一种常见的加速方式，所有大型网站都是用缓存，而缓存的数据则存储在散列表中。

广度优先搜索

广度优先搜索 （breadth-first search, BFS）

可以解决最短路径问题。

广度优先搜索是一种用于图的查找算法。可以帮助解决两类问题：

第一类：从节点A出发，有前往节点B的路径吗？

第二类：从节点A出发，前往节点B的哪条路径最短？（段数最少的路径）

实现方式—队列（queue）

查找你有没有朋友是经销商。

广度优先的运行时间为O(V+E) ，其中V为顶点数，E为边数。

图

有向图（directed graph）—带箭头

无向图（undirected graph）—不带箭头

下面两个图等价：