数据结构与算法（第2章 ：2.2 算法和算法分析）

1.算法

• ① 算法定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列

• ② 算法描述：自然语言、流程图、程序设计语言、伪码

• ③ 算法的特性：
  - 输入：有0个或多个输入
  - 输出：有一个或多个输出
  - 确定性：每一步的定义都是确切、无歧义的
  - 有穷性：算法应该在执行有穷步后结束
  - 有效性：每一条运算应足够基本

2.算法的评价

① 正确性

② 可读性

③ 健壮性

④ 高效性（时间代价和空间代价）

3.算法的时间复杂度

• ① 用依据该算法编制的程序在计算机上执行所消耗的时间来度量
• ② 一个高级语言程序在计算机上运行所消耗的时间取决于:

    ①依据的算法用何种策略
    ②问题的规模（主要因素）
    ③程序语言
    ④编译程序产生机器代码质量
    ⑤机器执行指令速度

4.事前分析法估算时间复杂度

①算法中基本语句重复执行的次数是问题规模n的某个函数，算法的时间度量记作：T（n）=O（f（n））

②渐进时间复杂度：随着n的增大，算法执行的时间的增长率和f（n）的增长率相同（n越大，算法执行时间越长

③方法

```
1.找出语句频度最大的那条语句作为基本语句
2.计算基本语句的频度得到问题规模n的某个函数f（n）
3.取其数量级用符号“O”表示
    ```

④时间复杂度按数量级递增顺序：常 < 对 < 幂 < 指 < 阶

5.算法的空间复杂度

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

②算法要占据的空间：

算法本身要占据的空间，输入，输出，指令，常熟，变量等

算法要使用的辅助空间

数据结构与算法（第2章 ：绪论 ---> 2.2 算法和算法分析）

原文：https://www.cnblogs.com/DongZang/p/12983258.html