目录
- 什么是算法
- 算法的五个重要特性
- 算法的执行时间
- 运算的分类
- 事前分析和事后测试
- 函数表达式的数量级
- 限界函数
- 上界函数、下界函数、均值函数
什么是算法
-
什么是算法
算法就是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算
算法的五个重要特性
-
算法的五个重要特性
确定性：确切的定义
能行性：可行
输入
输出
//只满足前四个称作 计算过程 例：操作系统
有穷性：一个算法总是在执行了有穷步的运算之后终止
算法的执行时间
-
算法的执行时间：
算法的 执行时间 是算法中所有运算执行时间的总和
运算的分类
-
运算的分类：时间囿于常数的运算、时间囿于非常数的运算
时间囿界于常数的运算 ：执行时间是固定量，与操作数无关
基本算术运算，如整数、浮点数的加、减、乘、除，字符运算，赋值运算，过程调用等
时间非囿界于常数的运算 ：运算的执行时间与操作数相关，每次执行的时间是一个不定的量。
字符串操作：与字符串中字符的数量成正比，如字符串的比较运算（strcmp），记录操作：与记录的属性数、属性类型等有关
分析时间非囿界于常数的运算时，将其分解成若干时间囿界于常数的运算即可。
事前分析和事后测试
-
什么是事前分析和事后测试？各阶段的目标特点是什么？
事前分析 ：求出该算法的一个时间界限函数
事后测试 ：收集此算法的执行时间和实际占用空间的统计资料,事后测试与物理实现直接有关
算法分析主要集中于与物理实现无关的事前分析阶段——获取算法的理论时间/空间复杂度。
函数表达式的数量级
-
什么是函数表达式的数量级？数量级的大小怎么反应了算法复杂度的高低？
函数表达式的数量级（阶）
- 函数表达式中的最高次项的次数
- 在频率计数函数表达式中，数量级是衡量频率计数的“大小”的一种测度。
数量级从本质上反映了算法复杂度的高低
- 数量级越小，算法的复杂度越低，同等规模下算法执行时间越短。
- 数量级越大，算法的复杂度越高，同等规模下算法执行时间越长。
限界函数
-
什么是限界函数？怎么得来的？
限界函数通常是关于问题规模n的特征函数(特征函数是通过分析算法的控制逻辑得来的，是对算法所用运算执行次数的统计结果。与使用的程序设计语言和计算机硬件无关)，被表示成Ο、Ω或Θ的形式。
限界函数用频率计数函数表达式中的最高次项表示限界函数，记为：g(n)。
★ g(n)通常是关于n的形式简单的函数式，如：logn，nlogn等
★ 不同算法的g(n)有不同的具体形式。
★ g(n)通常是对算法中最复杂的计算部分分析而来的。
★ g(n)忽略了函数表达式中次数较低的“次要”项，体现了算法复杂性的最本质特征。
★ g(n)通常取单项的形式。
上界函数、下界函数、均值函数
- 限界函数：上界函数、下界函数、均值函数的定义和性质
- n是问题规模的某种测度。
- f(n)是与机器及语言有关的量。
- g(n)是事前分析的结果，一个形式简单的函数，与频率计数有关、而与机器及语言无关。
上界函数 ：O，表示小于等于|f(n)|<=c|g(n)|，f(n)=O(g(n)
下界函数 ：Ω，表示大于等于|f(n)|>=c|g(n)|，f(n)=Ω(g(n)
均值函数 ：Θ，c1 |g(n)|<=|f(n)|<=c2 |g(n)|，
f(n)=Θ(g(n)
总是试图求出数量级最小的g(n)作为f(n)的上界函数，即， g(n)应该尽量接近函数f(n)——紧确(tight bound )。如
若：3n+2=O(n2) 则是松散的界限；
而：3n+2=O(n) 就是紧确的界限。
数量级越小，限界越精确。
根据上界函数的特性，可以将算法分为：多项式时间算法和指数时间算法
多项式时间算法 ：可用多项式函数对计算时间限界的算法。
常见的多项式限界函数有：
Ο(1) < Ο(logn) < Ο(n) < Ο(nlogn) < Ο(n2 ) < Ο(n3 )
指数时间算法 ：计算时间用指数函数限界的算法。
常见的指数时间限界函数：
Ο(2n ) < Ο(n!) < Ο(nn )
9. 理解定理1.2 P76
10. 掌握数学归纳法、反证法、反例法等证明方法