算法

定义

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

输入（0/m）
输出（0/1）
有穷性
确定性
可行性

描述

语言方式
图形方式
表格方式

性能标准

正确性：要求算法能够正确地执行预定的功能和性能要求

没有语法错误
对于合法的输入能产生满足要求的输出
对于非法输入能得出满足规格说明的结果
对于精心选择的，刁难的测试有满足要求的输出

可使用性：要求算法能够很方便的使用

抽象数据类型或模块化
输入输出通过参数表显式传递
少用公用或全局变量
一个算法一个功能

可读性：算法应当是可读的

算法逻辑（清晰、简单、结构化）
变量名、函数名
注释

健壮性：要求在算法中加入对输入参数、打开文件、对文件记录、子程序调用状态进行自动检错、报错并通过与用户对话来纠错的能力
简单性：指一个算法所采用数据结构和方法的简单程度。

简单->出错率低->可靠性高

效率：指算法执行时计算机资源的消耗，包括存储和运行时间的开销。

算法效率的度量方法

分析算法占用的资源

CPU 时间：时间性能分析
内存控件: 空间性能分析

算法效率的度量的目的：分析算法的时空效率以便改进算法性能

后期测试

主要通过在算法中的某些部位插装时间函数来测定算法完成某一规定功能所需要的时间

必须实现编制好程序
算法的运行时间以来于所用的计算机系统、编辑器、可用存储空间大小
算法的测试数据设计器困难，并且程序的运行时间往往还与测试数据的规模有很大的关系

事前估计

在计算机程序编制前，依据统计方法对算法进行估算

算法采用的策略、方法
编译产生的代码质量
问题的输入规模
机器执行指令的速度

算法的复杂性的度量属于事前估计

时间复杂度
控件复杂度

计算时间复杂度

{
  let s = 1
  for (var i = 0; i < n; i++) {
    s += i
    return s
  }
}

一次性执行所需的程序步骤	执行次数	程序步骤
0	1	0
1	1	1
2	n+1	2n+2
1	n	n
1	1	1
0	1	0

总程序步骤数：

T(n) = 0+1+2n+2+n+1+0
     = 3n+4

大 O 记号

算法 ​

定义 ​

分类 ​

描述 ​

性能标准 ​

算法效率的度量方法 ​

后期测试 ​

事前估计 ​

计算时间复杂度 ​

算法

定义

分类

描述

性能标准

算法效率的度量方法

后期测试

事前估计

计算时间复杂度