第一章 算法的世界

作者: Qiuo 分类: 数据结构 发布时间: 2020-03-31 18:52
算法的概念:
有限的步骤解决数学问题的程序
为了解决某项工作或某个问题,所需要有限数量的机械性或重复性指令与计算步骤

算法的条件:
输入:0个或多个输入,这些输入必须有清楚的描述和定义
输出:至少有一个输出结果,不可以没有输出结果
有限性:有限步骤后一定会结束,不会无限循环
明确性:每个指令必须是简洁明确的
有效性:步骤清楚可行

时间复杂度O(f(n)):
1 < log2n < n < nlog2n < n2 < n3 < 2n
算法复杂度只是执行次数的估计,并非真实的执行次数

常见算法:
分治法,
将大问题分解为小问题,逐个击破
如快速排序法,希尔排序法,合并排序法,基数排序法,二分查找,插值查找,
递归算法,大整数乘法

递归法,
自己调用自己的功能
两个条件:
1.可以反复执行的递归过程
2.可以离开递归执行的窗口
如n!,堆栈,斐波那契数列,汉诺塔,二叉树遍历,BFS,DFS

贪心法,
采取当前状态下的最佳选择,一步步解答,慢慢接近目标,当达到某一步骤不能前进时,算法停止,就是尽可能快的求得更好的解.
经常用于找出图的最小生成树(MST),最短路径和哈夫曼编码

动态规划法,
如果一个问题答案与子问题相关的话,就能将大问题拆解为各个小问题,其中与分治法最大不同的地方是可以将每个子问题的答案被存储起来,以供下次求解直接取用,这样的做法不但能减少再次计算的时间,并可以将这些解组合成大问题的解答,故而动态规划感可以解决重复计算的问题.
如改进版的斐波那契数列

迭代法,
无法使用公式一次求解,需要使用迭代
如求最大公约数,冒泡排序法,矩阵相加,矩阵相乘,转置矩阵,链表


枚举法,
如回溯法,列出某一范围5的倍数,选择排序法,顺序查找法

回溯法("智能"枚举法)
一旦发现不正确的数值,就不再递归到下一层,而是回溯到上一层,以节省时间.
特点是在搜索过程中寻找解,发现不满足条件就返回,尝试别的路径,避免无效搜索
如老鼠走迷宫,八皇后的问题



发表评论

电子邮件地址不会被公开。

标签云