算法学习一

算法期末复习

一、算法分析基础

1、 求解问题的步骤

① 分析问题

② 设计算法

✧ 建立数学模型

✧ 算法设计与选择

✧ 确定算法指标

✧ 算法分析

③ 编写程序

④ 调试程序

⑤ 结果整理

⑥ 文档编制

2、 算法的定义

一组有穷的规则

☞解决问题的方法和过程

☞是任何定义好了的计算程式

✧ 取某些值或值的集合作为输入

✧ 产生某些值或值的集合作为输出。

3、 算法的特征：

☞输入

✧ 可以没有输入，输入取自于某个特定对象的集合

☞输出

✧ 不可以没有输出，输出是同输入有特定关系的量

☞确定性/明确性

✧ 每一条指令无二义性

✧ 算法只有一个入口和一个出口

☞能行性/可行性

✧ 算法描述的操作是可以通过已经实现的基本运算执

行若干次来实现的

☞有限性/有限性

✧ 算法总能在执行有限步之后终止，且每一步都在有

穷时间内完成

4、算法描述

☞描述两个N阶矩阵相乘的算法，并给出渐近的时间复杂度

for(i=0; i<n; i++):                               //n+1
    for(j=0; j<n; j++):                           //n(n+1)
        {c[i][j] = 0;                             //n^2
            For(k=0; k<n; k++):                  //n^2*(n+1)
                c[i][j]+=a[i][k] *b[k][j];              //n^3
}

5、算法的时间效率

☞算法执行时间大多花在循环和递归上

☞算法执行的基本运算次数与问题规模相关

☞对算法执行时间的估计通常使用事前分析的方法

☞度量算法执行时间的估计不应考虑编程语言和计算机系统的因素

6、算法的时间复杂度

☞执行过程中所需要的基本运算次数

☞用数量级形式表示的算法执行时间

☞要想在电脑上扩大所处理问题的规模，有效的途径是降低算法的计算复杂度

☞算法时间复杂度的计算方式包括

✧ 计算循环次数

✧ 基本运算的次数

✧ 计算程序步

7、平均时间复杂度

8、算法的有效性

☞能在一定的时空资源限制内将问题解决

☞能比其他已知算法都更快地将问题解决

9、三种渐近符号Ο,Ω, Θ

（1）当忽略较低数量级项和常数因子时，三种符号为算法运行时间提供了什么界？

✧ 渐近上界

✧ 渐近下届

✧ 准确界

（2）对于给定的两个函数，要求能够判定谁是谁的什么界，并给出理由（根据渐近符号的含义）

运行时间的渐近上界：O：

设函数和是定义在非负整数集合上的正函数，如果存在正整数和正常数，使得当时，有：

就称的阶至多是，记为：

运行时间的渐近下界： W

设函数和是定义在非负整数集合上的正函数，如果存在正整数和正常数，使得当时，有：

就称的阶至少是，记做

运行时间的准确界： Q

设函数和是定义在非负整数集合上的正函数，如果存在正整数和正常数和，使得当时，有：

就称的阶是，记为：

此时称与同阶

【定理1】如果是次多项式，且，则。

【定理2】如果是次多项式，且，则。

【定理3】：如果是次多项式，且，则。

算法按时间复杂度分类：

① 多项式时间(polynomial time)算法

– 渐近时间复杂度有多项式时间限界的算法

① 指数时间(exponential time)算法

– 渐近时间复杂度为指数函数限界的算法

1<sqrt(n)<log(n)<n<nlog(n)<n^2<n^3...<2^n<....n!<n^n

10、测试和调试

☞测试是针对样本数据检查程序输出

☞调试只能指出有错误，不能指出不存在错误

☞算法的正确性验证是通过程序的测试和调试进行排错

11、好算法的评价标准：

☞代码短？

☞运行速度快？

☞占用空间少？

☞时间复杂度低？

12、算法设计的质量指标

☞ 正确性

✧ 算法应满足具体问题的需求；

☞ 可读性

✧ 算法应该好读，以有利于读者对程序的理解；

☞ 健壮性

✧ 算法应具有容错处理

✧ 当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果

☞ 时间效率

✧ 算法执行的时间

✧ 一般与问题规模相关

☞ 空间效率/存储量需求

✧ 算法执行过程中所需要的最大存储空间

✧ 一般与问题规模相关

13、☞堆排序的最差情形下为Θ( log )

☞快速排序平均情形下为Θ( log )

☞插入排序在最好情况下为Θ()

14、算法的分类

☞按计算时间分

✧ 多项式时间算法

✧ 指数时间算法

☞按计算机领域分

✧ 数值计算算法

✧ 非数值计算算法

不是所有问题都有算法

---

About Me

QQ 群：1094019526    tg 群：QQ 群里有

联系我请加 QQ 好友 (1362449059)，注明添加缘由

文章内容来源于 TOM 的学习笔记，部分整理自网络，若有侵权或不当之处还请谅解

本文版权所有，转载请标明出处，谢谢