算法设计与分析W14-随机算法

VIP免费

2025-01-13 2 0 1.57MB 81 页 5.9玖币

侵权投诉

Randomized Algorithm

随机算法

放宽算法正确求解的条件：

将算法必须对所有可能输入都正确地求解问题的条

件放宽

只要求算法可能不正确的解能够相对安全地忽略掉，

比如说它的出现可能性非常低

不要求对于特定的输入，算法的每一次运行的输出

都必须相同

随机算法可以做如下定义：

在接收输入的同时，为了随机选择的目的，还接收

一串随机比特流并且在运行过程中使用该比特流的

算法

一个随机算法在不同的运行中对于相同的输入可以

有不同的结果；由此得出对于相同的输入两次不同

的随机算法的执行时间可能不同

随机算法

随机算法通常有两个优点：

较之那些所知的解决同一问题最好的确定性算

法，随机算法所需的运行时间或空间通常常小

一些；

观察迄今为止已经发明的各种随机算法，发现

这些算法总是易于理解和实现

排序问题：

Quicksort

问题：对一个包含

个数的集合

按照升序排序

方法：递归

找到元素

，使得

S\{x}=S1!S2

，其中

包含

比

小的元素，

包含其他元素

递归排序

与

，升序输出

中的元素，输出

，再升序输出

中的元素

枢轴（

pivot

）

排序问题：

Quicksort

A[j]>x

问题：对一个包含

个数的集合

按照升序排序

方法：递归

找到元素

，使得

S\{x}=S1!S2

，其中

包含

比

小的元素，

包含其他元素

递归排序

与

，升序输出

中的元素，输出

，再升序输出

中的元素

i j

A[j]"x

排序问题：

Quicksort

运行时间：

#$%&'#$(&)#$%*(*+&),$%&

最坏情况

: #$%& ' #$-& ) #$%*+& ) ,$%&

#$%&' ,$%𝟐&

A: n, n-1, n-2, …., 3, 2, 1

平均复杂度

: #$%&' ,$%./0%&

随机排序算法

算法

RandQS

输入：数组

输出：按照升序排列的

中的元素

从

中均匀随机选择元素

，即

中每个元素以相

同概率被选择

;

通过将

中每个元素与

比较，确定包含比

小的元

素的集合

和包含比

大的元素的集合

；

对

与

做递归排序，然后输出排序后的

S1, x

，排

序后的

S2.S2

分析比较次数：比较次数的期望

RandQS

时间复杂度分析

分析比较次数：比较次数的期望

ü S(i)

：表示

中次序为

的元素（第

小元素），

S(1)

：

中最小元素

S(n)

：

中最大元素

随机变量

Xij

：

Xij = 12

因此，总比较次数为

4𝒊#𝟏

𝒏4𝒋'𝒊 5𝒊𝒋

数学期望为：

E( 4𝒊#𝟏

𝒏4𝒋'𝒊 5𝒊𝒋 ) = 4𝒊#𝟏

𝒏4𝒋'𝒊 6$5𝒊𝒋)

用

pij

表示

S(i)

和

S(j)

在执行中进行比较的概率，得

E[Xij] = pij71+(1-pij)70 = pij

，当

S(i)

与

S(j)

在执行中进行了比较

，否则

pij =

？

RandQS

时间复杂度分析

分析比较次数：比较次数的期望

ü S(i)

：表示

中次序为

的元素（第

小元素），

S(1)

：

中最小元素

S(n)

：

中最大元素

随机变量

Xij

：

Xij = !1

因此，总比较次数为

∑𝒊"𝟏

𝒏∑𝒋&𝒊 𝑿𝒊𝒋

数学期望为：

E( ∑𝒊"𝟏

𝒏∑𝒋&𝒊 𝑿𝒊𝒋 ) = ∑𝒊"𝟏

𝒏∑𝒋&𝒊 𝑬(𝑿𝒊𝒋)

用

pij

表示

S(i)

和

S(j)

在执行中进行比较的概率，得

E[Xij] = pij×1+(1-pij)×0 = pij

，当

S(i)

与

S(j)

在执行中进行了比较

，否则

pij =

？

将

RandQS

的执行过程看作一个二分树

，其中每个结

点由

中不同元素标记

üT

的

根对应在第

步选择的元素

üx

的左子树包含

中的元素，

的右子树包含

中

的元素

üS1

与

的结构由

RandQS

在

与

上的执行过程

递归确定

RandQS

时间复杂度分析

S1S2

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

5.9 玖币 0人已下载

立即下载 VIP免费下载

摘要：

RandomizedAlgorithm随机算法随机算法u放宽算法正确求解的条件：ü将算法必须对所有可能输入都正确地求解问题的条件放宽ü只要求算法可能不正确的解能够相对安全地忽略掉，比如说它的出现可能性非常低u不要求对于特定的输入，算法的每一次运行的输出都必须相同u随机算法可以做如下定义：ü在接收输入的同时，为了随机选择的目的，还接收一串随机比特流并且在运行过程中使用该比特流的算法u一个随机算法在不同的运行中对于相同的输入可以有不同的结果；由此得出对于相同的输入两次不同的随机算法的执行时间可能不同随机算法u随机算法通常有两个优点：ü较之那些所知的解决同一问题最好的确定性算法，随机算法所需的运行时...

展开>> 收起<<

算法设计与分析W14-随机算法.pdf

共81页,预览17页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

算法设计与分析W14-随机算法

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: