本文内容：
1、什么是算法？
2、算法分析基础？
3、文集列表
建议数据结构和算法分开来学，这里只有算法，没有什么是数据结构！数据结构在这里; --->> 点我
1、什么是算法？
算法：是一系列指令，是指一系列解决问题的明确指令；给定规范的输入，有限时间内会获得要求的输出；--【算法设计与分析基础】
Wiki : In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems.
[ 在数学与计算机科学领域里面，算法是指解决一类问题的明确规范。]
ME : 其实不管是指令还是规范，算法就是解决问题的方法，但这个方法是明确的，明确不代表唯一；
图解：
算法设计与分析基础
看看别人的答案：
Wiki-Algorithm
学习算法?：
知乎-怎样学算法
知乎-有哪些学习算法的网站推荐？
知乎-如何系统地学习算法？
国外视频教程：
Coursera-普林斯顿大学【Part I】
Coursera-普林斯顿大学【Part II】
练习算法的网站：
LeetCode
hihoCoder
LintCode
2、算法分析基础？
这话很好！
算法分析：指对算法运行时间与存储空间的效率的研究；
时间效率也被称为时间复杂度，指出正在运行的程序运行得多快；
空间效率也被称为空间复杂度，指出正在运行的程序占用多少存储空间；
运行时间度量单位：
cop: 指计算机一个算法基本操作的执行时间【近似值】；
C(n): 指算法需要执行基本操作的次数；
n: 指输入的规模；
增长次数，而运行时间分析里面，显然最重要的就是 C(n) 的分析：
不同的 C(n)
从表可以看出，log n 是增长速度最慢的，而 2n / n ! 都是增长飞速的；
最差情况、平均情况、最优情况
最差情况：当输入规模为 n 时，算法在最坏情况下的效率；
【即，当输入规模为 n 时，那种类型的输入会导致基本操作次数 ( C(n) ) 达到最大值】【Cworst ( n ) 】
最优情况：当输入规模为 n 时，算法在最优情况下的效率；
【即，当输入规模为 n 时，那种类型的输入会导致基本操作次数 ( C(n) ) 达到最小值】
平均情况：当输入规模为 n 时，算法在平均情况下的效率；
【即，当输入规模为 n 时，随机类型的输入导致的基本操作次数 ( C(n) ) 的平均值】【即为，通常情况下的操作次数】
研究的重点：
三个渐近符号：[ Ο ] [ Ω ] [ Θ ]
渐近符，是为了简化函数，分析影响函数增加次数最大的部分；
注意
[ Ο ] [ 读：欧 ] :【小于等于号】
定义：
图示：
[ Ω ] [ 读：欧妹（mei 第一声）嘎（ omega 美[oʊˈmegə] ） ]:【大于等于号】
定义：
图示：
[ Θ ] [ 读：嘚（dei 第一声）塔（ theta 美[ˈθetə, ˈθi-] ） ]:【等于号、区间号】
定义：
图示：
渐近符定理：
基本渐近效率类型：
（非）递归算法的数学分析:
-
非递归算法的数学分析方案：
-
Ep 1:
解析：
1、确定输入规模：就是数组的个数 n ；
2、确定核心基本操作：函数功能是得到最大值，而得到最大值的核心就是比较谁更大，即对应函数的 if A[i] > maxval ;
3、确定核心基本操作是否只依赖于输入规模：if A[i] > maxval 其中 i 就是属于 [0 ~ n - 1]，maxval 就是 A[i] 的一个值，而且 if 的顶层 for 循环是从 0 ~ n - 1 的循环也同样只依赖于输入规模 n ，所以基本操作只依赖于输入规模 n ；
4、建立求和表达式：因为每一次的 for 循环都要执行一次 if 比较，即核心基本操作的执行次数就等于 for 循环的循环次数，即 n-1 ; 则有：C(n) = (n - 1) * 1 = n- 1 ;
5、得到闭合公式或增长次数：C(n) = n - 1 ∈ Θ(n) ;
-
递归算法的数学分析方案：
-
Ep:
解析：
1、确定输入规模：就是数组的个数 n ；
2、确定核心基本操作：函数功能是得到某个数的阶乘，而阶乘就是做连续的乘法，即对应函数的 F(n - 1) * n ，即乘法是基本操作;
3、检查基本操作在不同的输入下的执行情况，显然这里的输入不管那种类型，乘法运算还是那个乘法运算；
4、建立递推关系与初始条件：
初始条件就是递归停止的条件，这里是 if n = 0；
递推式：
M(n - 1) : 对应 F(n - 1) 的执行次数；
1 : 对应 F(n - 1) * n 的执行次数；
因为终止条件成立的时候，没有执行乘法操作，所以 M(0) = 0 ;
5、解递推式：M(n) = M(n - 1) + 1 ;
最终结果
算法的经验分析
还有一个是算法可视化的方法来做算法分析，知道就好；
3、文集列表
-
排序算法
《算法：冒泡排序》
《算法：选择排序、插入排序、希尔排序》（未写）
《算法：归并排序》（未写）
《算法：快速排序》（未写）
《算法：堆排序》（未写）
《算法：计数排序》（未写）
《算法：桶排序》（未写）
《算法：基数排序》（未写） -
查找算法
《算法：顺序查找》（未写）
《算法：二分查找》（未写）
《算法：插值查找》（未写）
《算法：斐波那契查找》（未写）
《算法：树表查找》（未写）
《算法：分块查找》（未写）
《算法：哈希查找》（未写） -
图论算法
《算法：图论基础，无向图、有向图》（未写）
《算法：深度优先搜索 [ 无向图 ] 》（未写）
《算法：广度优先搜索 [ 无向图 ] 》（未写）
《算法：狄克斯特拉算法 [加权图] 》（未写）
《算法：最小生成树 [ 加权无向图 ]》（未写）
《算法：最短路径（旅行商问题） [ 加权有向图 ]》（未写）
《算法：拓扑排序 [ 有向无环图 ] 》（未写）
《算法：网络流（最大流） [ 有向图 ]》（未写）
《算法：NP 完全性（多项式、背包问题） [ 有向图 ]》（未写）
《算法：匈牙利方法（分配问题）》（未写）
《算法：近似算法》（未写） -
数论算法
《算法：数论基础》（未写）
《算法：最大公约数》（未写）
《算法：模运算》（未写）
《算法：解模线性方程》（未写）
《算法：中国余数定理》（未写）
《算法：元素的幂》（未写）
《算法：多项式插入》（未写）
《算法：最小二乘估计法》（未写）
《算法：方程求解》（未写） -
几何算法
《算法：线段相交》（未写）
《算法：凸包问题》（未写）
《算法：最近对问题》（未写）
《算法：球面弧长》（未写） -
正则表达式
《算法：正则表达式简述》（未写） -
多线程、矩阵运算
《算法：多线程实现》（未写）
《算法：矩阵运算》（未写） -
算法技巧
《算法：贪婪算法》（未写）
《算法：分治算法》（未写）
《算法：动态规划》（未写）
《算法：随机化算法》（未写）
《算法：回溯算法》（未写）
参考书籍/文章：
书籍：《算法设计与分析基础 美 莱维汀 第3版》
书籍：《算法（第四版）》
书籍：《算法精解_C语言描述(中文版)》
书籍：《数据结构与算法分析—C语言描述》
书籍：《算法图解》
书籍：《算法导论(原书第3版) 中文完整版》
书籍：《啊哈！算法》
文章：《七大查找算法》
如有错漏，还望指出，不胜感激！
网友评论