当前位置：文档之家 › 算法与计算复杂性课程(7)概率算法

算法与计算复杂性课程(7)概率算法

  • 格式：pdf
  • 大小：331.92 KB
  • 文档页数：54

下载文档原格式

  / 54

合集下载

算法设计与分析课程教学大纲

算法设计与分析课程教学大纲

算法设计与分析课程教学大纲【适用专业】计算机科学与技术【课时】理论课时：32【学分】 2【课程性质、目标和要求】《算法设计与分析》是计算机科学与技术专业的专业课。

无论是计算科学还是计算实践，算法都在其中扮演着重要角色。

本课程的教学目的是讲授在计算机应用中常常遇到的实际问题的解法，讲授设计和分析各种算法的基本原理、方法和技术，培养学生对算法复杂性进行正确分析的能力。

课程基本要求是⑴掌握算法分析的基本概念和理论。

⑵掌握算法设计技术和分析算法以及算法复杂性。

【教学时间安排】本课程计 2 学分，理论课时32, 学时分配如下：【教学内容要点】第一章算法引论一、学习目的要求1．了解算法的计算复杂性分析方法2．理解算法分析的基本理论3．掌握算法分析的基本概念二、主要教学内容1. 算法的基本概念2. 表达算法的抽象机制3. 采用Java语言与自然语言相结合的方式描述算法的方法4. 算法的计算复杂性分析方法第二章递归与分治策略一、学习目的要求1．理解典型范例中递归与分治策略应用技巧2．掌握递归与分治策略3．掌握数学归纳法证明算法正确性方法二、主要教学内容1. 递归的概念2. 分治法的基本思想3. 二分搜索技术4. 大整数的乘法5. Strassen阵乘法6. 棋盘覆盖7. 合并排序8. 快速排序9. 线性时间选择10. 最接近点对问题11. 循环赛日程表第三章动态规划一、学习目的要求1．理解典型范例中动态规划算法的设计思想2．掌握动态规划算法的基本要求以及算法的设计要点二、主要教学内容1. 矩阵连乘问题2. 动态规划算法的基本要素3. 最长公共子序列4. 最大子段和5. 凸多边形最优三角剖分6. 多边形游戏7. 图像压缩8. 电路布线9. 流水作业调度10. 0—l背包问题11. 最优二叉搜索树12. 动态规划加速原理三、课堂讨论选题1. 最长公共子序列2. 0—l背包问题第四章贪心算法一、学习目的要求1．了解贪心算法的理论基础及基本要素2. 理解典型范例中贪心算法的设计思想3. 掌握贪心算法的设计要点二、主要教学内容1. 活动安排问题2. 贪心算法的基本要素3. 最优装载4. 哈夫曼编码5. 单源最短路径6. 最小生成树7. 多机调度问题8. 贪心算法的理论基础三、课堂讨论选题1. 最优装载2. 单源最短路径第五章回溯法一、学习目的要求1．理解回溯法的效率分析方法2．掌握回溯法的算法框架和应用技巧二、主要教学内容1. 回溯法的算法框架2. 装载问题3. 批处理作业调度4. 符号三角形问题5. n后问题6. 0—l背包问题7. 最大团问题8. 图的m着色问题9. 旅行售货员问题10. 圆排列问题11. 电路板排列问题12. 连续邮资问题13. 回溯法的效率分三、课堂讨论选题1. 0—l背包问题2. 图的m着色问题第六章分支限界法一、学习目的要求1．理解分支限界法的基本思想2．掌握典型范例中分支限界法的应用技巧二、主要教学内容1. 分支限界法的基本思想2. 单源最短路径问题3. 装载问题4. 布线问题5. 0-1背包问题6. 最大团问题7. 旅行售货员问题8. 电路板排列问题9. 批处理作业调度三、课堂讨论选题1. 0-1背包问题2. 批处理作业调度第七章概率算法一、学习目的要求1．理解概率算法的基本思想2．掌握典型范例中概率算法的应用技巧二、主要教学内容1. 随机数2. 数值概率算法3. 舍伍德算法4. 拉斯维加斯算法5. 蒙特卡罗算法第八章 NP完全性理论一、学习目的要求1．了解P类与NP类问题2．了解典型的NP完全问题二、主要教学内容1. 计算模型2. P类与NP类问题3. NP完全问题4. 一些典型的NP完全问题第九章近似算法一、学习目的要求1．掌握近似算法的基本思想2．掌握常用近似算法的应用二、主要教学内容1. 近似算法的性能2. 顶点覆盖问题的近似算法3. 旅行售货员问题近似算法4. 集合覆盖问题的近似算法5. 子集和问题的近似算法第十章算法优化策略一、学习目的要求1．掌握算法优化策略2．掌握算法优化的基本方法二、主要教学内容1. 算法优化策略的比较与选择2. 动态规划加速原理3. 问题的算法特征4. 优化数据结构5. 优化搜索策略【教学（实验）内容要点】算法设计与分析实验是算法设计与分析课的一个实践性教学环节。

如何迅速计算复杂的概率问题

如何迅速计算复杂的概率问题

如何迅速计算复杂的概率问题概率问题在数学和统计学中扮演着重要的角色，但是对于一些复杂的概率问题，我们可能会感到头疼。

然而，有一些技巧和方法可以帮助我们迅速计算复杂的概率问题。

本文将介绍一些这样的方法，以帮助您更好地解决概率问题。

一、理解问题的要求在解决任何概率问题之前，我们首先需要清楚地理解问题的要求。

我们需要弄清楚问题中涉及到的事件、概率和相关的条件。

通过仔细阅读问题，理解问题的核心要求，可以帮助我们更好地解决问题。

二、使用基本的概率公式对于一些简单的概率问题，我们可以使用基本的概率公式来计算。

例如，如果我们要计算一个事件发生的概率，可以使用下面的公式：P(A) = n(A) / n(S)其中，P(A)表示事件A发生的概率，n(A)表示事件A中有利的结果的个数，n(S)表示样本空间中的总结果数。

通过使用这个公式，我们可以计算出事件发生的概率，从而解决一些简单的概率问题。

三、使用排列组合对于一些涉及到顺序和组合的概率问题，我们可以使用排列组合的方法来解决。

排列指的是从一组元素中选取一部分元素的顺序排列的方法；组合指的是从一组元素中选取一部分元素的组合方式。

例如，如果我们要计算从10个不同的球中选取3个球的排列数，可以使用排列公式：P(n,r) = n! / (n-r)!其中，P(n,r)表示从n个元素中选取r个元素的排列数，!表示阶乘。

同样地，如果我们要计算从10个不同的球中选取3个球的组合数，可以使用组合公式：C(n,r) = n! / (r!(n-r)!)通过使用排列组合的方法，我们可以快速计算出一些涉及到顺序和组合的概率问题。

四、使用条件概率和贝叶斯定理在一些复杂的概率问题中，我们可能需要考虑到条件概率和贝叶斯定理。

条件概率是指在发生了某个事件的条件下，另一个事件发生的概率。

贝叶斯定理是一个重要的概率公式，可以用于计算在给定一些条件下的事件发生的概率。

条件概率和贝叶斯定理可以帮助我们解决一些复杂的概率问题，尤其是当涉及到多个事件和条件时。

第5章 算法与复杂性

第5章 算法与复杂性
对于一个算法的评价，通常要从正确性、可理解性、 健壮性、时间复杂度(Time Complexity)及空间复杂 度(Space Complexity)等多个方面加以衡量。 1．算法的时间复杂度 时间复杂度是度量时间的复杂性，即算法的时间效率 的指标。 2．算法的空间复杂度 算法的空间复杂度是度量空间的复杂性，即执行算法 的程序在计算机中运行时所占用空间的大小。
5.7 可计算性理论基础
研究计算的可行性和函数算法的理论，又称算法 理论，是算法设计与分析的基础，也是计算机科 学的理论基础。可计算性是函数的一个特性。
5.8 NP问题
NP(Non-deterministic Polynomial)问题是非确定性多 项式问题，是指算法无法直接计算出结果，只能通过进 行一些有选择的“猜算”来得到结果。 NP问题的研究结果有两种可能： 一种是找到了求解问题的算法； 另一种就是求解问题的算法是不存在的，那么就要从数
钥，通常有两个密钥，称为“公钥”和“私钥”，它 们两个必须配对使用，否则不能打开加密文件。
5.10 加密算法
常见加密算法有如下： (1)DES(Data Encryption Standard)：数据加密标准，速 度较快，适用于加密大量数据的场合。 (2)3DES(Triple DES)：是基于DES，对一块数据用3个不 同的密钥进行3次加密，强度更高； (3)RC2和RC4：用变长密钥对大量数据进行加密，比DES 快。 (4)IDEA(International Data Encryption Algorithm)国 际数据加密算法，使用128位密钥提供非常强的安全性。 (5)RSA：由RSA公司发明，是一个支持变长密钥的公共密 钥算法，需要加密的文件块的长度也是可变的。 (6)DSA(Digital Signature Algorithm)：数字签名算法， 是一种标准的DSS(数字签名标准)。

第一讲：计算复杂性理论

第一讲：计算复杂性理论

大多数研究者认可 的包容关系
L m
计算复杂度的影响因素
简化模型：模型2
计算复杂度的影响因素
简化模型：模型3。
计算复杂度的影响因素
建模假设 例：高空抛球的运动轨迹。 ----抛物线模型 假设1.没有空气阻力； 假设2.地面是平面。 ----椭圆模型
计算复杂度的影响因素
探索空间1 探索空间1---解的近似度、满意度
例：0—10之间的整数解：1-9共9个可行解（一维） 0—10之间的实数解：精确到小数点后6位 共有107个可行解（一维）； 107n个可行解（n维）
n! 10141世紀 → 10120世紀 102551世紀 → 102530世紀
问题与算法
每个問題都可能有多个算法存在． 每个算法的计算量（速度）都不同。 例： 赝品金币問題： 问题：9個外观完全一样的金币.，有一个是假的 （重量轻）． 提问：用天秤来鉴别真伪，天秤需要使用几次？
贋品金币問題算法 問題算法
优化技术与方法
計算量(1) 計算量
＋,－,×,÷ 比較：≠，≤，≥，＜，＞ 5种基本演算都是用1step 可以实现. 実際上,×比＋多占用時間. 「四舍五入」不算基本演算.
計算量(2) 計算量
｛a1, a2,..., an｝：n個整数 Q1. 求和（1）： a1+a2+･･･+an. 1 + +a n-1 steps → O(n)算法. Q2. 求和（2）： (1) 2×a1+･･･+ 2×an , 2n-1 steps→ O(n)算法. (2) 2×(a1+･･･+an) , n steps→ O(n)算法.
尚未确信能否用多項式時間算法求解的问题的 集合称为NP （non-deterministic polynomial）问题 某一个问题不属于NP问题的証明 如能够找到一个多項式時間算法 （簡単） 某一个问题属于NP问题的証明 可以归结为某一类既知的NP类问题（现阶段7类））

概率算法

概率算法

1
9.1.2 随机数发生器
一、产生随机数的公式：
⎧ d0 = d ⎪ ⎨ d n = b d n −1 + c ⎪ a = d / 65536 n ⎩ n n = 1, 2 , L
（9.1.1）
产生 0~65535 的随机数 a1 , a 2 , L 序列，
b 、 c 、 d 为正整数， d 称为所产生的随机序列的种子。
∑
∑
≤ n+
n −1 n −1 ⎤ 4⎡ ⎢ i + i⎥ n ⎢ i = n / 2 +1 i = n / 2 ⎥ ⎡ ⎤ ⎦ ⎣ ⎣ ⎦
∑
∑
≤ n+
n −1 n −1 ⎤ 4⎡ ⎢ i + i⎥ n ⎢ i= n / 2 i = ⎡n / 2 ⎤ ⎥ ⎣ ⎡ ⎤ ⎦
∑
∑
= n+
8 n
i = ⎡n / 2 ⎤
9.2
舍伍德（Sherwood）算法
一、确定性算法的平均运行时间
T A ( x ) ：确定性算法 A 对输入实例 x 的运行时间。 X n ：规模为 n 的所有输入实例全体。
算法 A 的平均运行时间：
2
T A(n) =
x∈ X n
∑T
A ( x) /
|Xn |
存在实例 x ∈ X n ， T A ( x ) >> T A ( n ) 。 例：快速排序算法 当输入数据均匀分布时，运行时间是 Θ ( n log n ) 。 当输入数据按递增或递减顺序排列时，算法的运行时间变坏 二、舍伍德算法的基本思想 消除不同输入实例对算法性能的影响，使随机算法 B 对规模为 n 的每一个实例 x ∈ X n ， 都有：

算法设计与分析ppt课件

算法设计与分析ppt课件
2
ACM国际大学生程序设计竞赛
ACM国际大学生程序设计竞赛（英文 全称：ACM International Collegiate Programming Contest（ACM-ICPC或 ICPC）是由美国计算机协会（ACM）主办 的，一项旨在展示大学生创新能力、团队 精神和在压力下编写程序、分析和解决问 题能力的年度竞赛。经过30多年的发展， ACM国际大学生程序设计竞赛已经发展成 为最具影响力的大学生计算机竞赛。赛事 目前由IBM公司赞助。
第3章 动态规划 3.1 矩阵连乘问题 3.2 动态规划算法的基本要素 3.3 最长公共子序列 3.4 最大子段和 3.5 凸多边形最优三角剖分 3.6 多边形游戏 3.7 图像压缩 3.8 电路布线 3.9 流水作业调度 3.10 0-1背包问题 3.11 最优二叉搜索树 3.12 动态规划加速原理
7
1.1 算法与程序
算法：是满足下述性质的指令序列。
输 入：有零个或多个外部量作为算法的输入。 输 出：算法产生至少一个量作为输出。 确定性：组成算法的每条指令清晰、无歧义。 有限性：算法中每条指令的执行次数有限，执行
每条指令的时间也有限。
程序：是算法用某种程序设计语言的具体实现。
4
教材与参考书
教 材：
◦ 算法设计与分析(第三版) 王晓东，2007年 5月，电子工业出版社。
参考书：
◦ 徐士良编，C常用算法程序集，华大学出版 社，1998年
◦ 霍红卫编，算法设计与分析 西安电子科技 大学出版社，2005年
◦ 卢开澄编，计算机算法导引，清华大学出 版社，2003年
5
部分目录
算法分析是计算机领域的“古老”而“前沿” 的课题。
10

概率算法

1、概率算法：允许算法在执行的过程中随机的选择下一个计算步骤。

2、在多数情况下，当算法在执行过程中面临一个选择是：随机性选择常比最优选择省时，因此概率算法可在很大程度上降低算法复杂性。

3、概率算法的一个基本特征是对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果(所需时间或计算结果)。

4、概率算法包括：▪数值概率算法：求解数值问题的近似解，精度随计算时间增加而不断提高▪舍伍德算法：消除算法最坏情形行为与特定势力之间的关联性，并不提高平均性能，也不是刻意避免算法的最坏情况行为▪拉斯维加斯算法：求解问题的正确解，但可能找不到解▪蒙特卡罗算法：求解问题的准确解，但这个解未必正确，且一般情况下无法有效判定正确性5、随机数：随机数在概率算法设计中扮演着十分重要的角色。

在现实计算机上无法产生真正的随机数，因此在概率算法中使用的随机数都是一定程度上随机的，即伪随机数。

6、线性同余法是产生伪随机数的最常用的方法。

7、数值概率算法：通常用于数值问题的求解中，求解数值问题的近似解，精度随计算时间增加而不断提高例如：设有一半径为r的圆及其外切四边形。

向该正方形随机地投掷n个点。

设落入圆内的点数为k。

由于所投入的点在正方形上均匀分布，因而所投入的点落入圆内的概率为224rr∏。

所以当n足够大，4kn∏=程序一：double Darts(int n){ // 用随机投点法计算π值static RandomNumber dart; int k=0;for (int i=1;i <=n;i++) {double x=dart.fRandom(); double y=dart.fRandom(); if ((x*x+y*y)<=1) k++;}return 4*k/double(n);}计算定积分，同样的道理可以阐述到10()I f x dx=⎰表示曲线以下面积，那么落入曲线下面积的概率为()11000{()}()f xrP y f x dydx f x dx≤==⎰⎰⎰，即可知I mn≈8、舍伍德算法：设A 是一个确定性算法，当它的输入实例为x 时所需的计算时间记为tA(x)。

算法的计算复杂性概念

算法的计算复杂性概念
计算复杂性是一个相当普遍的概念，用来衡量算法的复杂程度及其所需要的计算和存储资源。

它指出了通过解决一个特定问题所需要的资源数量和时间，是计算机科学领域中应用非常广泛的计算时间和空间复杂度理论。

计算复杂性的基本思想是：给定的算法的运行时间，由其所执行的基本步骤的重复次数决定。

这些步骤机会包括读写输出、内存操作、比较和逻辑判断等。

每一次的重复，都会消耗算法所需的资源。

算法的运行时间，在某程度上可以用消耗的资源数量来衡量。

计算复杂性概念被用来衡量算法空间和时间复杂度，以及评价算法效率，它是一种定量量度。

运行时间和空间复杂度由大O表示法来表示，Big O表示法在数学里描述函数增加量的时候，使用主要步骤多少来表示算法的复杂程度。

算法中最耗时的基本步骤是核心步，而计算复杂性可以衡量算法的效率，并评估算法的运行性能。

计算复杂性的概念历经多年，今天已经成为计算机科学领域的核心技术，深受计算性能分析专家、软件开发者和算法设计者的重视。

它不仅能够帮助识别算法效率的关键瓶颈，而且能够用精准的度量标准来比较两个算法的性能，帮助推进算法的改进，提高计算性能。

因此计算复杂性是一个极为重要的计算机科学概念，它能够用精确的方式衡量算法的复杂程度，用于评估算法的性能，以及帮助算法设计者和开发者识别算法缺陷并进行改进。

计算理论计算复杂性ppt课件

((x1)x2(x3)) (x2(x3)x4x5) ((x4)x5) • 合取范式cnf (conjunctive normal form)
3cnf: 每个子句文字数不大于3, 2cnf: 每个子句文字数不大于2
可满足问题SAT
• 可满足性问题: SAT = { <> | 是可满足的布尔公式 }
• 思想: 将字符串对应到布尔公式 利用接受的形式定义.
• 过程: 任取ANP, 设N是A的nk时间NTM. w(|w|=n), N接受w
N有长度小于nk的接受格局序列 能填好N在w上的画面(一个nknk表格) f(w)可满足 • 结论: SAT是NP完全的
N接受w能填好N在w上的画面
# q0 w0 w1 … wn #
2)若0,1都在带上,重复以下步骤. O(n)
3) 检查带上0,1总数的奇偶性,
若是奇数,就拒绝.
O(n) log n
4) 再次扫描带,
第1个0开始,隔1个0删除1个0; O(n)
第1个1开始,隔1个1删除1个1.
总时间:
5)若带上同时没有0和1,则接受. O(n) O(nlogn)
否则拒绝.”
{0k1k|k0}TIME(nlogn)
快速验证
HP = {<G,s,t>|G是包含从s到t的 哈密顿路径的有向图}
CLIQUE={<G,k>|G是有k团的无向图} 目前没有快速算法,但其成员是可以快速验证的. 注意:HP的补可能不是可以快速验证的. 快速验证的特点: 1. 只需要对语言中的串能快速验证. 2. 验证需要借助额外的信息:证书,身份证.
• 二元可满足性问题: 2SAT = { <> | 是可满足的2cnf }

算法设计与分析-绪论


回溯法的算法框架 实例分析

０－１背包问题 ＴＳＰ问题 N皇后问题 连续邮资

回溯法的效率分析
基础算法部分教学安排（6/10）

第六章：分支限界法

分支限界法的基本思想 实例分析

单源最短路径问题 装载问题 布线问题
基础算法部分教学安排（7/10）

第七章：概率算法


分析总结阶段
方案是否可行 是否满足预期要求 与其他方案相比，本方案有哪些优点（通过实验数 据说明），有哪些问题？如何进行改进？ ——提交工程设计论文


6000字左右 遵照标准科技论文格式 严禁抄袭!
工程论文要求



题目 作者 摘要 文献综述 典型问题 方案设计 实验分析 研究过程中发现的问题总结 结论与感想 参考文献 附件说明

如不交作业，该组同学的该次作业成绩以0分计；

每次上传作业中，除规定的课程作业外，还需注明本次作业 的负责同学姓名,学号 以及作业的分工； 每周四中午12：00前交作业，迟交一律不收

工程设计要求（1/5）


准备阶段
确定要研究的课题； 在组内进行分工； 拟订工作计划； ——提交研究小组组成情况说明，课题名称，分工以 及工作计划

考核方式

平时成绩（40%）；

请假以课前书面假条为准
小组汇报、实验+考勤

期末考试或工程设计（60%）
平时作业的分组安排

平时作业的分组安排


按2-3人/组进行分组 自由组合； 每组选出一位同学作为联系人,该联系人在10月10日前将本 组成员名单、联系方式上传到作业目录下； 作业按组上交，成绩按组评定 由联系人负责作业和实验报告。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

∑ ≤ 2
n−1
T(i) + O(n)
n i=n/2
注意n为奇数，上式没有T(n/2)项 11
预期时间估计（续）
Hale Waihona Puke ∑ T(n) ≤2
n−1
T (i) + tn
n i=n/2
设T (k) ≤ ck 对一切 k < n为真,则
T (n) ≤ 2 [c n + c( n + 1) + ... + c(n − 1)] + tn n2 2
2
伪随机数生成算法
伪随机数生成算法 ---线性同余法 生成伪随机序列为{ai}, i= 0,1,…, n,…, 0<ai<m
⎩⎨⎧aa0n
=d = (ban−1
+
c ) mod
m
n = 1,2,...
模数：m, 机器最大数.
乘数：b, 2≤b<m，计算前给定
常数：c, 0≤c<m，计算前给定
种子：d, 0≤d<m, 计算时随机给出
9
例2 随机选择算法
算法 RandSelect(A, p, r, k) //从A[p..r]中选第k小 1. if p=r then return A[p] 2. i←Random(p, r) 3. 以A[i]为标准划分A 4. j←划分后小于等于A[i]的数构成数组的大小 5. if k≤ j 6. then return RandSelect(A, p, p+j-1, k) 7. else return RandSelect(A, p+j, r, k-j)
B 的平均复杂性
∑ t B
(n)
=
|
1 Xn
|
tB
x∈X n
(
x)
=
t A (n)
+
s(n)
14
Sherwood算法总结
算法能得到正确的解 算法比确定型算法简单 算法的平均性能与确定型算法一样 算法改善了最坏情况的期望运行时间 运行时间基本与输入实例无关 确定算法最坏情况在随机选择出现的概率接近0 实现途径
概率算法
随机数 概念 伪随机数生成算法
几种主要的概率算法 Sherwood算法 Las Vegas算法 Monte Carlo算法
1
伪随机数
随机数与伪随机数
概率算法中要进行随机选择，需要大量随机数. 通常根据某种规则生成随机数，这些随机数不 是真正随机的，但在一定程度上可以模拟随机 数，一般叫做伪随机数 随机变量X的取值范围是(0,1)且对任意的0<a<1, P{0<X≤a}=a, 则称X服从(0,1)上的均匀分布
3
乘同余法
⎩⎨⎧aa0 n==dban−1 mod m
n = 1,2,...
参数：c = 0，d ≠ 0，m=231-1, b=75
实例：d=1
16,807, 1,622,650,073, 1,144,108,930, 101,027,544, ……
282,475,249, 984,943,658, 470,211,272, 1,457,850,878
10
预期时间估计
假设随机选择时，1..n中每个数被选的概率相 等，并且假设第k个数总是出现在划分后两个数 组中较大的数组（最坏情况的上界）.那么，随机
选择算法的预期时间为
T (n) ≤ 1 (T (n − 1) + T (n − 2) + ... + T ( n + 1)
n
2
+ T ( n ) + T ( n + 1) + ... + T (n − 1)) + O(n) 22
7
Sherwood算法
例1 快速排序的随机算法
算法 RandQuicksort(A,p,r) 1. if p<r then 2. q←RandPartition(A,p,r) 3. RandQuicksort(A,p,q-1) 4. RandQuicksort(A,q+1,r)
算法 RandPartition(A,p,r)
=
2c
(n 2
+
n
− 1)
n 2
+
tn
n
2
= c ( 3n − 1) + tn = 3cn − c + tn
22
42
≤ 3cn + tn = ( 3 + t )cn ≤ cn 取c ≥ 4t即可
4
4c
12
算法比较
拟中位数选择算法 最坏情况 O(n) 平均情况 O(n)
随机算法 平均时间 O(n) 最坏情况 O(n2) 每次恰好选到边界元素 与实例无关，只与选择有关 概率很小，可以忽略 期望时间 O(n)
1. i←Random(p,r)
2. A[i]↔A[p]
3. return Partition(A,p,r)
8
算法比较
确定型排序算法 Quicksort 最坏情况下时间为O(n2) 平均情况下为 O(nlogn)
确定型排序+选择算法 如果选用中位数进行划分, 时间为O(nlogn)
随机快速排序算法 期望时间 O(nlogn) 最坏情况概率非常小，在实际应用中可以忽略
5.
return
5
确定型算法与随机算法
1. 特点： 确定型算法: 对某个特定输入的每次运行过程 是可重复的，运行结果是一样的. 随机算法：对某个特定输入的每次运行过程是随机 的，运行结果也可能是随机的.
2. 随机算法的优势： 在运行时间或者空间需求上随机算法比确定型算法 往往有较好的改进 随机算法设计简单
4
离散型伪随机数的产生
输入：P={ai, ai+1, …, aj}, 输出：伪随机数ak∈P
算法：Random(i, j) // 产生ai,…,aj之间随机数
1. 产生伪随机数x
//乘同余法
2. n ← j−i+1
//总个数n
3. for k←1 to n do // 检查第k个区间
4. if x/m ≤ k/n then x←ak+i-1 // 0<x<m
6
随机算法复杂性度量
随机算法A对于规模为n的某个给定的实例I 的一次 执行的时间与另一次可能不一样.
随机算法A对于某个规模为n的实例I 的运行时间的 期望：算法A反复求解实例I 的平均时间.
一般情况下，许多随机算法对于规模为n的不同的实 例，运行时间的期望都一样，因此这个值代表随机 算法的平均时间的期望.
13
预期复杂度分析
设A为求解问题π的确定型算法，B为对应的Sherwood
算法，对于输入x的计算时间分别记为tA(x), tB(x). 令 Xn={ x | x为π的实例, |x|=n }
输入等概率分布情况下，A的平均时间复杂度
t
A
(n)
=
|
1 Xn
|
∑tA
x∈X n
(
x)
B在实例x的时间期望 tB ( x) = t A (n) + s(n)