没有合适的资源？快使用搜索试试~ 我知道了~

文库首页开发技术其它麻省理工学院-算法导论 .Introduction.to.Algorithms（课件）

麻省理工学院-算法导论 .Introduction.to.Algorithms（课件）

麻省理工学院-算法导论

.Introduction.to.Algorithms（课件）

需积分: 10 1 下载量 148 浏览量 2008-12-12 22:26:09 上传评论收藏 155KB PDF 举报

温馨提示

试读

29页

麻省理工学院-算法导论 .Introduction.to.Algorithms（课件）

资源详情

资源评论

Introduction to Algorithms

6.046J/18.401J/SMA5503

Lecture 2

Prof. Erik Demaine

Day 3 Introduction to Algorithms L2.2

Solving recurrences

• The analysis of merge sort from

Lecture 1 required us to solve a

recurrence.

• Recurrences are like solving integrals,

differential equations, etc.

o Learn a few tricks.

• Lecture 3: Applications of recurrences.

Day 3 Introduction to Algorithms L2.3

Substitution method

1. Guess the form of the solution.

2. Verify by induction.

3. Solve for constants.

The most general method:

Example: T(n) = 4T(n/2) + n

• [Assume that T(1) = Θ(1).]

• Guess O(n

) . (Prove O and Ω separately.)

• Assume that T(k) ≤ ck

for k < n .

• Prove T(n) ≤ cn

by induction.

Day 3 Introduction to Algorithms L2.4

Example of substitution

))2/((

)2/(

)2/(4

)2/(4)(

nnccn

nnc

≤

−−=

+≤

desired – residual

whenever (c/2)n

– n ≥ 0, for example,

if c ≥ 2 and n ≥ 1.

desired

residual

Day 3 Introduction to Algorithms L2.5

Example (continued)

• We must also handle the initial conditions,

that is, ground the induction with base

cases.

•

Base: T(n) = Θ(1) for all n < n

, where n

is a suitable constant.

• For 1 ≤ n < n

, we have “Θ(1)” ≤ cn

, if we

pick c big enough.

This bound is not tight!

剩余28页未读，继续阅读

评论收藏

内容反馈

麻省理工学院-算法导论 .Introduction.to.Algorithms（课件）

评论0

最新资源

麻省理工学院-算法导论 .Introduction.to.Algorithms（课件）

评论0

最新资源

相关推荐

[麻省理工学院-算法导论].Introduction.to.Algorithms（课件）

麻省理工学院-算法导论(Introduction.to.Algorithms)

麻省理工学院-算法导论].Introduction.to.Algorithms

[麻省理工学院-算法导论].Introduction.to.Algorithms

[麻省理工学院-算法导论].Introduction.to.Algorithms.-.Lecture.Notes

[麻省理工学院-算法导论].Introduction.to.Algorithms,.Second.Edition

[麻省理工学院-算法导论].Introduction.to.Algorithms.-.Homework

[麻省理工学院-算法导论].Introduction.to.Algorithms.-.Homework.rar

[麻省理工学院-算法导论].Introduction.to.Algorithms.-.Lecture.Notes 算法导论-课堂笔记 讲义

Introduction.to.Algorithms [麻省理工学院-算法导论]

算法导论，Introduction to Algorithms

算法导论 .Introduction.to.Algorithms,

算法导论《Introduction to Algorithms》

算法导论Introduction.to.Algorithms

麻省理工学院-算法导论.Introduction.to.Algorithms,.Second

麻省理工学院-算法导论.Introduction.to.Algorithms.-.Lecture.Notes

麻省理工学院-算法导论(MIT - Introduction to Algorithms)\[麻省理工学院-算法导论].Introduction.to.Algorithms,.Second.Edition.part1.rar

[麻省理工学院-算法导论].Introduction.to.Algorithms--PPT

算法导论 (Introduction.to.Algorithms()

算法导论 Introduction.to.Algorithms

算法导论[Introduction.to.Algorithms]

[算法导论].[Introduction to Algorithms]

[麻省理工学院-算法导论].Introduction.to.Algorithms,.Second.Edition.chm

[麻省理工学院-算法导论].Introduction.to.Algorithms.-.Test.

[麻省理工学院-算法导论].Introduction.to.Algorithms.-.01.Analysis.of.algorithm

[算法导论].[Introduction.to.Algorithms]

Introduction to Algorithms(算法导论)

[麻省理工学院-算法导论].Introduction.to.Algorithms.-.Lecture.Notes 算法导论-课堂笔记讲义