[NOTE-DS]数据结构概述与大O记号

思考问题

1、算法的特性是什么
2、如何评估一个算法的性能
3、什么是大O记号,使用其应注意什么?是否还有其他评估方式?

概述

**计算 **
主要研究对象,寻规律 技巧,达到有效高效计算 computer sicenice

绳索计算机
输入:人给直线及其一点
输出:垂线
算法:采用12段线方式 埃及人

尺规计算机
任给一条线段 如果找出两个切分点均匀切分
算法:弄三个相等的射线段 完事之后做平行线

算法:
正确性
确定性
可行性
有穷性 参考递归例子

程序 不等于 算法 (例如死循环 栈溢出)

如何设计好的算法?

正确,健壮,可读,最重要的是效率(速度快、空间少) 算法+数据结构 = 程序

计算模型

性能测试: 度量 To measure is to know

算法分析:
1、正确性
2、成本 运行时间+所需存储空间 如何度量?如何比较?

划分等价类:问题实例的规模,往往决定计算成本

特定算法,同一问题 :规模不同可能不同,规模相同也有可能成本不同,所以也要关注最坏情况;特定问题,不同算法:算法不同可能不同。

那么如何计算呢?实验室统计?但是不足够 不同规模 类型 语言 体系结构 操作系统等

客观的评判
1、需要抽象出一个理想平台或模型
2、不再依赖上述种种具体的因素 直接准确描述 测量并评论算法

如何客观评判呢?

  • 图灵机模型TM:
    Tape 依次均匀的划分为单元格,各注一个有某一字符,默认为#

Alphabet 字符的种类有限

Head 总是对准某一单元格,并可读取和改写其中的字符没经过一个节拍,可转向左侧或右侧的邻格

State TM总是处于悠闲中状态的某一种 没经过一个节拍,可(按照规则)转向另一种状态

Transition Function (q,c;d,L/R,p)若当前状态为q且当前字符为c,则当前字符改写为d;
转向左侧/右侧邻格;转入p状态一旦转入特定的状态’h’,则停机

图灵机实例:二进制非负整数加1

  • RAM模型

无限的空间 寄存器顺序编号,总数没有限制,每一个基本操作仅需要常数时间

RAM实例:Floor

图灵机模型与RAM模型对比:
均是一般计算工具的简化与抽象,使我们可以独立于具体平台,对算法效率做出可信的比较与评判

总结:
在这些模型中,算法的运行时间 ~~~ 算法需要执行的而基本操作次数 抛开了硬件环境

复杂度标注

大O记号(big-O notation)上界(针对性能的悲观预测)

关心足够大的问题,注重考查成本的趋势,常系数可以忽略,低次项可以忽略

其他标示
* Ω 下界 针对性能的乐观预测
* seita 针对性能的平均预测

高效解
* 常数O(1) 算法效率最高 不含转向(循环调用递归等)必顺序执行既是O1
* 对数O(logn)算法非常有效 复杂度无限接近与常数
* 常底数无所谓
* 常数次幂无所谓
* 对数多项式
* O(n的c次方)线性:所有O(n)类函数
*
较低效解
* O(2的n次方)指数 成本增长极高

例子:2-subset

算法分析

  • 正确性(不变性 单调性)+复杂度
  • 去粗存精
  • C++等高级语言的基本指令,均等效于常数条RAM的基本指令
  • 分支转向:goto
  • 迭代循环:for while 本质上是if goto
  • 调用+递归:本质上也是goto

复杂度分析的主要方法
* 迭代:级数求和
* 递归:递归跟踪+递推方程
* 猜测+验证

级数(最好再看一遍,就知道复杂度)
* 算数级数:与末项平方同阶
* 幂方级数:比幂次高出一截
* 几何级数:与末项同阶
* 收敛级数:O(1)

循环,使用面积的方式来看复杂度

非极端元素+冒泡排序

正确性的证明
* 问题:算法是否必然结束?至多迭代多少趟
* 不变性:经k纶扫描交换后,最大的k歌元素必然就位
* 单调性:经k纶扫描交换后,问题规模缩减至n-k
* 正确性:经过至多n趟,算法必然终止,能给出正确解答

封底估算 Back Of the envelopse calculation

0条留言