算法和算法分析

算法特性：一个算法必须具备一下五个重要的特性。

• 有穷性：一个算法必须总是在执行有穷步之后结束，切每一步都在有穷时间内完成。
• 确定性：算法中每一条指令必须有确切的含义，没有二义性，在任何条件下，只有唯一的一条执行路径，即对于相同的输入只能得到相同的输出。
• 可行性：算法是可执行的，算法描述的操作可以通过已经实现的基本操作执行有限次来实现。
• 输入：一个算法有零个或多个输入。
• 输出：一个算法有一个或多个输出。

算法设计的要求：

• 正确性(Correctness)
• 可读性(Readability)
• 健壮性(Robustness）
• 高效性(Efficient)

算法分析：
一个好的算法必须首先要具备正确性，然后是健壮性、可读性，在几个方面都满足的情况下，主要考虑算法的效率，可以通过算法的效率高低来评判不同算法的优劣程度。
算法效率以下两个方面来考虑：

1. 时间效率：指的是算法锁耗费的时间。
2. 空间效率：指的是算法执行过程中所耗费的存储空间

• 时间效率和空间效率有时候是矛盾的。

算法时间效率的度量

• 算法时间效率可以依据该算法编制的程序在计算机上执行所消耗的时间来度量。
• 两种度量方法
  • 事后统计
    • 将算法实现，测算其时间和空间开销。
    • 缺点：编写程序实现算法将花费较多的时间和精力；所得时间结果依赖于计算机的软硬件等环境因素，掩盖算法本身的优劣。
  • 事前分析
    • 对算法所消耗资源的一种估算方法

事前分析方法：

• 一个算法的运行时间是指一个算法在计算机上运行所耗费的时间大致可以等于计算机执行一种简单的操作（如赋值、比较、移动等）所需的时间与算法中进行的简单操作次数乘积。

算法运行时间 = 一个简单操作所需要的时间 x 简单操作次数

• 也即算法中每条语句的执行时间之和

算法运行时间=$$Σ$$每条语句执行的次数x该语句执行一次所需的时间

渐进空间复杂度

• 空间复杂度：算法所需存储空间的度量，记作：S(n) = O(f(n)) 其中n为问题的规模（或大小）

算法要占据的空间

• 算法本身需要占据的空间，输入/输出，指令，常数，变量等。
• 算法要使用的辅助空间

​

算法的时间复杂度和空间复杂度计算方法学习：
时间复杂度：https://www.bilibili.com/video/BV1nJ411V7bd?p=8
空间复杂度：https://www.bilibili.com/video/BV1nJ411V7bd?p=9
​

设计好算法的过程
抽象数据类型 = 数据的逻辑结构 + 抽象运算 （运算的功能描述）