算法设计与分析W4-减治+变治

VIP免费

2025-01-13 0 0 912.59KB 94 页 5.9玖币

侵权投诉

Last Section

Complete Development of an Algo.

•1 Statement of the problem

•2 Development of a Model

•3 Design of the algorithm

•4 Correctness of the algorithm

•5 Implementation

•6 Analysis and complexity of the algorithm

•7 Program testing

•8 Documentation

Methodology

•Algo. A → Algo. B

–Method

–Principle

–Control

•Algo. B → Algo. C

–Method

–Control + Data Structure

•Algo. C → Algo. D

–Data Structure

Divide and Conquer

•MINMAX:

2n –2 vs. 3n/2 –2

•二分搜索:

算法BINARYSEARCHREC在n 个元素组成的已

排序数组中搜索某个元素所执行的元素比较次数

不超过；

非递归；

•合并排序： nlogn

•寻找第 k 小元素：20cn

•划分算法与快速排序：n-1;n(n-1)/2

 

1log n

合并排序效率

(a,c非负整数，b,d,x非负常数，n=ck)：

f(n) =d 若n=1

=af(n/c)+bnx若n>=2

的解是

f(n)= bnxlogcn + dnx若a=cx

f(n)= 若a<>cx

dc





























log

寻找第 k 小元素

SELECT

输入：n个元素的数组A[1…n]和整数k, 1 ≤ k ≤n。

输出：A中的第k 小元素。

•select(A, 1, n, k)

Procedure select (A, low, high, k)

1. p ← high – low + 1

2. if p < 44 then 将A 排序return (A[k])

3. 令q = 。将A分成q组，每组5个元素。如果5不整除p, 则排除剩余的元素。

4. 将q 组中的每一组单独排序，找出中项。所有中项的集合为M.

5. mm ← select(M, 1, q, ) //mm 为中项集合的中项

6. 将A[low…high] 分成三组

A1 = {a | a < mm}

A2 = {a | a = mm}

A3 = {a | a > mm}

7. case

| A1 | ≥ k: return select (A1, 1, |A1|, k)

| A1| + | A2| ≥ k: return mm

|A1| + |A2| < k: return select(A3, 1, |A3|, k-|A1| - |A2|)

8. end case

 

5/p

 

2/q

Select 效率

•1、2均为Θ(1);

•3 为Θ(n);

•4为Θ(n);

•5为T( )

•6为Θ(n);

•7为T(0.7n+1.2)

设0.7n+1.2<= , n>=44

T(n)<=c 若n<44

<=T( )+T( )+cn 若n>=44

T(n)<=20cn (c为一足够大的常数)

 

5/n

 

n75.0

 

5/n

 

4/3n

划分算法

SPLIT

输入：数组A[low…high].

输出：（1）输出A[low] in Position 的重新排列的数组A;

•(2) 划分元素A[low]的新位置w.

• 1. i← low

• 2. x←A[low]

•3. for j← low + 1 tohigh

•4. if A[ j ] ≤ x then

•5. i← i + 1

•6. if i ≠j then 互换A[ i ] 和A [ j ]

•7. end if

•8. end for

•9. 互换A[low] 和A[i]

• 10. w← i

•11. return A 和w571683

划分算法

SPLIT

输入：数组A[low…high].

输出：（1）输出A[low] in Position 的重新排列的数组A;

•(2) 划分元素A[low]的新位置w.

• 1. i← low

• 2. x←A[low]

•3. for j← low + 1 tohigh

•4. if A[ j ] ≤ x then

•5. i← i + 1

•6. if i ≠j then 互换A[ i ] 和A [ j ]

•7. end if

•8. end for

•9. 互换A[low] 和A[i]

• 10. w← i

•11. return A 和w

•n-1次元素比较

571683

快速排序

QUICKSORT

输入：n个元素的数组A[1…n].

输出：按非降序排列的数组A 中的元素。

Quicksort(A, 1, n)

procedure quicksort (A, low, high)

1. if low < high then

2. SPLIT (A[low…high], w) {w 为A[low]的新位置}

3. qicksort(A, low, w-1)

4. quicksort(A, w + 1, high)

5. end if

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

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

5.9 玖币 0人已下载

立即下载 VIP免费下载

摘要：

LastSectionCompleteDevelopmentofanAlgo.•1Statementoftheproblem•2DevelopmentofaModel•3Designofthealgorithm•4Correctnessofthealgorithm•5Implementation•6Analysisandcomplexityofthealgorithm•7Programtesting•8DocumentationMethodology•Algo.A→Algo.B–Method–Principle–Control•Algo.B→Algo.C–Method–Control+Data...

展开>> 收起<<

算法设计与分析W4-减治+变治.pdf

共94页,预览19页

还剩页未读，继续阅读

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

算法设计与分析W4-减治+变治

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: