《算法导论》基础章节中一些概念
2022-06-07 本文已影响0人
Sun东辉
-
算法是什么？
- 非形式地说，算法就是定义良好的计算过程，该过程取一个或一组值作为输入，并产生出一个或一组值做出输出。这样，算法就是把输入转换成输出的计算步骤的一个序列。
- 维基百科对于算法的定义是：“算法，在数学（算学）和计算机科学之中，指一个被定义好的、计算机可施行其指示的有限步骤或次序，常用于计算、数据处理和自动推理。算法是有效方法，包含一系列定义清晰的指令，并可于有限的时间及空间内清楚的表述出来。”
- 算法中的指令描述的是一个计算，它执行时从一个初始状态和初始输入（可能为空）开始，经过一系列有限而清晰定义的状态最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。包括随机化算法在内的一些算法，都包含了一些随机输入。
-
为什么要学习算法？
- Linux 内核核心开发者 Robert Love 在 Quora 上的回答：“数据结构与算法的良好基础不是对每个数据结构都知道细节怎么实现，都背下来大 O 复杂度和摊销复杂度，当然知道这些非常好，只是你在工作中很少用到它们，你的职业生涯里几乎不可能让你实现一个红黑树和节点删除算法。但是，你必须知道什么时候 BST(二叉排序树)对于一个问题是个有效的解法”，所以，学习《算法导论》的目标，是知道应该在什么时候用什么样的数据结构和算法。
-
算法能够解决哪些问题？
- 地图的寻路算法、因特网的数据传输路径、公共密钥加密技术和数字签名技术等等。
-
什么是算法分析？
- 算法分析即对一个算法所需要的资源进行预测。内存、通信带宽或计算机硬件等资源偶尔会是我们主要关心的，但通常，我们主要关心测度的计算时间。
-
为什么要进行算法分析？
- 可以通过分析几种候选算法，去掉几个较差的算法。
- 算法的运行时间是指在特定输入时，所执行的基本操作数（或步数）。
-
为什么一般考虑用最坏情况运行时间来评估算法的执行效率？
- 一个算法的最坏情况运行时间给出了任何输入下运行时间的上界。
- 对某些算法，最坏情况经常出现。
- “平均情况”往往与最坏情况大致一样差。
