🐱🏍 算法的定义
对特定问题求解方法和步骤的一种描述，它是指令的有限序列。其中每个指令表示一个或多个操作。
简而言之算法就是解决问题的方法和步骤。
🎍算法的描述
算法可以用以下几种方式描述：
- 自然语言【英文、中文】；
- 流程图【传统流程图、NS流程图、框图】；
传统流程图为框图，NS流程图也称为盒图
- 伪代码(类C语言)；
类C语言介于伪码语言和程序设计语言之间的一种表示形式，保留了C语言的精华，不拘泥于C语言的语法细节，同时也添加了一些C++的成分。
特点：便于理解，阅读能方便的转换成C语言。
- 程序设计(C、Java…)。
🎫程序与算法
程序 = 数据结构 + 算法
算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法。
程序是某种程序设计语言对算法的具体实现。
-
数据结构通过算法来实现操作。
-
算法根据数据结构设计程序。
👘算法的特性
-
有穷性：算法在执行有限步骤之后，自动结束而不会出现无限循环，并且每一个步骤都在可接受的时间范围内完成。
当然这里的有穷并不是纯数学意义的，而是在实际应用中合理的、可以接受的“边界”。你说你写一个算法，计算机需要算上20年，一定会结束，他在数学上是有穷的，媳妇都熬成婆了，算法的意义就不大了。
-
确定性：算法的每一个步骤都有确定的含义，不会出现二义性(不会有歧义)。
-
可行性：算法是可执行的，算法中的所有操作都可以通过已经实现的基本操作运算执行有限次来实现。
-
输入：一个算法有零个或多个输入。当用函数描述算法时，输入往往是通过形参表示的，在它们被调用时，从主调函数获得输入值。
-
输出：一个算法有一个或多个输出，它们是算法进行信息加工后得到的结果，无输出的算法没有任何意义。当用函数描述算法时，输出多用返回值或引用类型的形参表示。
🎍算法设计的要求
好的算法应该具有正确性、可读性、健壮性、时间效率高和存储量低的特征。
- 正确性(Correctness)：能正确的反映问题的需求，能得到正确的答案。
分以下四个层次：
-
a.算法程序没有语法错误；
-
b.算法程序对n组输入产生正确的结果；
-
c.算法程序对典型、苛刻、有刁难性的几组输入可以产生正确的结果；
-
d.算法程序对所有输入产生正确的结果；
但我们不可能逐一的验证所有的输入，因此算法的正确性在大多数情况下都不可能用程序证明，而是用数学方法证明。所以一般情况下我们把层次3作为算法是否正确的标准。
-
可读性(Readability)：算法，首先应便于人们理解和相互交流，其次才是机器可执行性。可读性强的算法有助于人们对算法的理解，而难懂的算法易于隐藏错误，且难于调试和修改。
-
健壮性(Robustness)：当输入的数据非法时，好的算法能适当地做出正确反应或进行相应处理，而不会产生一些莫名其妙的输出结果。【健壮性又叫又名鲁棒性, 即使用棒子粗鲁地对待他也可以执行, 类似于Java预料到可能出现的异常并对其进行捕获处理】
-
(高效性（Efficiency）)时间效率高和存储量低
🛒算法分析
一个 好的算法首先要具备正确性，然后是健壮性，可读性，在几个方面都满足的条件下，主要考虑算法的效率，通过算法的效率高低来评判不同算法的优劣程度。
(时间效率)运行时间的长短和(空间效率)占用内存空间的大小是衡量算法好坏的重要因素。
- 时间效率
指的是算法所耗费的时间。
- 空间效率
指的是算法执行过程中所耗费的存储空间。
时间效率和空间效率有时候是互相矛盾的。
👕算法时间效率的度量
算法时间效率可以依据该算法编制的程序在计算机上执行所消耗的时间来度量。
两种度量方法
1. 事后统计
将算法实现，测算其时间和空间开销。
缺点：编写程序实现算法将花费较多的时间和精力；所得的结果依赖于计算机的软硬件等环境因素，掩盖算法其本身的优劣。
2. 事前分析
对算法所消耗资源的一种估算方法。
- 通常采用事前分析估算法.
一个算法的运行时间是指一个算法在计算机上运行所耗费的时间大致等于计算机执行一种简单的操作（如赋值、比较、移动等）所需要的时间与算法中进行的简单操作的次数乘积。
算法运行时间 = 一个简单的操作所需的时间 * 简单的操作次数
也即算法中每条语句的执行时间之和
大写Σ（Sigma [西格玛]）用于数学上的总和符号，指求和
算法运行时间 = Σ每条语句的执行次数 * 该语句执行一次所需时间。
其中每条语句执行次数也称语句频度，所以公式可以表示为
算法运行时间 = Σ每条语句频度 * 该语句执行一次所需时间。
语句的执行要由源程序经编译程序翻译成目标代码，目标代码经装配再执行，因此语句执行一次实际所需的具体时间是与机器的软、硬件环境（如机器速度、编译程序质量等）密切相关的，它与算法无关。
所以，我们可以假设执行每条语句所需的时间均为单位时间。此时对算法的运行时间的讨论就可转化为讨论该算法中所有语句的执行次数，即频度之和了。
例如：两个n * n的矩阵相乘的算法可描述为：
i从1~n首先判断条件是否成立，条件满足执行循环体并i++，i=n+1判断条件是否不满足，退出循环，判断n+1次循环体执行了n次
- 我们把算法所耗费的时间定义为该算法中每条语句的频度之和，则上述算法的时间消耗T(n)为：
T(n) = 2n³ + 3n² + 2n + 1
- 为了便于比较不同算法的时间效率，我们仅比较它们的数量级
例如：两个不同的算法，时间消耗分别是：
T₁(n) = 10n² 与 T₂(n) = 5n³
后者不如前者
评论区