2006年六月月 发布的文章

解决算法分析中递归问题的方法

当一个算法(如二分查找)中包含对自己的递归调用时,关于这个算法时间复杂性的分析最终都转化为一个递归方程的求解问题,而这样的算法不在少数。实际上这是数学领域的问题,但是计算机科学又怎么能脱离数学而存在呢?^_^ 数学是好东西呀,可惜自己在这方面造诣颇浅,今生之遗憾亚。^_^

还好,解决递归方程涉及的数学知识我还是能应付的了的^_^。在MIT算法导论中介绍了3种方法,我们这里就说说这三种方法!这些是基础,如果以后要深入研究算法的话,这些知识是必须要精通的;如果并不想在算法方面有所深入的话,多学些知识也没错。我本身也是在学习,像这类的知识一般都比较死性,有些记住了,就可以掌握了。

1、Substitution Method
这是一种使用数学归纳法推导证明的方法,其步骤为先假设一个解,然后带入到递归方程中,利用数学归纳法推导,以验证假设的解是否合理。我们拿ITA(Introduction to Algorithm)中的例子说明吧,比较保险^_^。
[Ex1.]
T(n) = 4T(n/2) + n,解这个递归等式,分析T(n)的渐近性。

解:(这里我们只来找上界)
我们假设T(1) = θ(1),猜测一个解T(n) = O(n^3),根据O符号的定义,我们得到对k < n, 有T(k) <= ck^3,把这个解代入到T(n) = 4T(n/2) + n,并进行推导得出:
T(n) = 4T(n/2) + n
     <= 4c((n/2)^3) + n
     = (c/2)n^3 + n
     = cn^3 – ((c/2)n^3 – n)
当c >= 2, n >= 1时,((c/2)n^3 – n) >= 0,这时T(n) <= cn^3,即T(n) = O(n^3);

我们再回过头来看看当n = 1时这个解是否成立,即证明一下T(1) = θ(1)。对于1 <= n < n0, θ(1) <= cn^3 (c足够大),即该推导出的解也满足初始条件,所以O(n^3)是T(n)的一个上界。但是O(n^3)是否是严紧的上界呢,我们不妨缩小上界范围再推导一次,这次我们猜测解为T(n) = O(n^2),根据O符号的定义,我们得到对k < n, 有T(k) <= ck^2,把这个解代入到T(n) = 4T(n/2) + n,并进行推导得出:
T(n) = 4T(n/2) + n
     <= 4c((n/2)^2) + n
     = cn^2 + n
     = cn^2 – (-n)
不能严格符合T(n) <= cn^2的定义,所以推导失败。但是失败是不是说明,T(n) = O(n^2)一定不成立呢?我们再做一次最后的努力,当出现上面的这种情况时,我们假设解仍为:T(n) = O(n^2),只是我们选择对k < n, 有T(k) <= ak^2 – bk,我们选择减去一个低阶的项,这不会影响到n足够大时的渐进性的,这里是一个常用的技巧。
T(n) = 4T(n/2) + n
     <= 4(a(n/2)^2 – b(n/2)) + n
     = an^2 – bn – (bn – n)
     <= an^2 – bn (当b >= 1时)

这样我们找到了严紧解T(n) = O(n^2)。

2、Iteration method(Recursion-tree method)
这个方法的思想是:"迭代地展开递归方程的右端,使之成为一个非递归的和式,然后通过对和式的估计来达到对方程左端即方程的解的估计"。而我们可以借助’树’的形式来帮助迭代展开的过程。

[Ex2.]
T(n) = T(n/4) + T(n/2)+ n^2;解这个递归等式,分析T(n)的渐近性。

解:
T(n) = n^2 + T(n/4) + T(n/2)
     = n^2 + {(n/4)^2 + T(n/16) + T(n/8)} + {(n/2)^2 + T(n/8) + T(n/4)}
     = …
     = n^2 {1 + 5/16 + (5/16)^2 + (5/16)^3 + … }
     = θ(n^2)

3、Master Method
这是一种典型的套用公式的方法,解决形如’T(n) = aT(n/b) + f(n)’递归方程形的解的方法。这种递归方程是一类分治法的时间复杂性所满足的递归关系,即一个规模为n的问题被分成规模均为n/b的a个子间题,递归地求解这a个子问题,然后通过对这a个子间题的解的综合,得到原问题的解。如果用T(n)表示规模为n的原问题的复杂性,用f(n)表示把原问题分成a个子问题和将a个子问题的解综合为原问题的解所需要的时间,我们便有方程’T(n) = aT(n/b) + f(n)’。

在f(n)的三类情况下,我们有T(n)的渐近估计式有三类情况:(log(b, a)表示以b为底的对数)
(1) 若对于某常数ε>0,有f(n) = O(n^log(b, a-ε)),即f(n)以慢于n^(log(b, a))的速率渐进增长,则T(n) = θ(n^(log(b, a));

(2) 若有f(n) = θ(n^log(b, a) * (lgn)^k),即f(n)以相似于n^(log(b, a))增长的速率渐进增长,则T(n) = θ(n^(log(b, a) * (lgn)^(k+1)),k为一常数,k >= 0;

(3) 若对于某常数ε>0,有f(n) = Ω(n^log(b, a+ε)),即f(n)以快于n^(log(b, a))的速率渐进增长,且对于某常数c > 1和所有充分大的正整数n有af(n/b) <= cf(n),则T(n) = θ(f(n))。

举例来说吧:

[Ex3.]
T(n) = 4T(n/2) + n,解这个递归等式,分析T(n)的渐近性。

解:对T(n) = 4T(n/2) + n我们得到a = 4, b = 2, f(n) = n, 计算得出n^(log(b, a) = n^(log(2, 4) = n^2,而f(n) = n = O(n^(2-ε)),此时ε= 1,根据Case (1),我们得到T(n) = θ(n^2)。

[Ex4.]
T(n) = 4T(n/2) + n^2,解这个递归等式,分析T(n)的渐近性。

解:对T(n) = 4T(n/2) + n^2,我们得到a = 4, b = 2, f(n) = n^2, 计算得出n^(log(b, a) = n^(log(2, 4) = n^2, f(n) = n^2 = θ(n^2 * (lgn)^0),即k = 0,这样按照Case (2),我们得到T(n) = θ(n^2 * (lgn)^(k+1)) = θ(n^2 * (lgn))。

[Ex5.]
T(n) = 4T(n/2) + n^3,解这个递归等式,分析T(n)的渐近性。

解:对T(n) = 4T(n/2) + n^3,我们得到a = 4, b = 2, f(n) = n^3, 计算得出n^(log(b, a) = n^(log(2, 4) = n^2, f(n) = n^3 = Ω(n^(2+ε),此时ε= 1,且4f(n/2) = (n^3)/2 <= cn^3(c >= 1/2),所以得到T(n) = θ(n^3)。

对于大部分人来说’Master Method’应该是最常用的,这几个Case可要牢牢记在心上才行哟。

突破英语句型之'不耻下问篇'

脱口而出,’不耻下问’乃英语学习之真精神也,这里我们要学习一些经典的’问句’。

一、How …?

1、How about …?
How about taking a walk?
How about parking here?
How about going for a trip?

2、How do you like … ?
How do you like living in China?
How do you like your new job?
How do you like my new car?

3、How much should I pay for …?
How much should I pay for the hotel room?
– Actually, it’s free.

4、How often do you …?
How often do you go on a vocation?
– I never had a chance to go on a vocation.

How often do you eat out?
– I eat out all the time. I hate to cook.

5、How can you …? (带有强烈个人感情色彩)
How can you stand such terrible weather?
How can you stand her nagging all the time?
How can you stand the pressure here?

How can you treat me like that?
How can you do such a stupid thing?
– I don’t know. I wasn’t thinking I guess.

6、How come …? (!其后接正常语序)
How come he failed the exam ? Isn’t he the best student in the class?
How come you never visit us any more?
How come I have to go to bed so early?

7、How long have you been …?
How long have you been learning English?
How long have you been in China?
How long have you been feeling like this?

How long have you been married?
How long have you been working here?
How long have you been a computer programmer?
How long have you been having this dream?
How long have you been waiting here?
How long have you been collecting stamps?
How long have you been a football fan?

8、How long will it take …?
How long will it take to get there?
How long will it take to make a million dollars?
How long will it take to rebuild New York city?
How long will it take to finish the project?
How long will it take to conquer English?
How long will it take to fly from Beijing to New York?

9、How do you know … ?
How do you know I can’t do it?
How do you know it won’t work?
How do you know which stocks to buy?
How do you know my name?

10、How are you getting along with …?
How are you getting along with your roommate?
How are you getting along with your colleagues?
How are you getting along with your new girlfriend?
How are you getting along with your new boss?
– OK, I guess. I really don’t see him that much.

二、What …?

1、What about …?
What about your future?
What about the new restaurant?
What about going together?

2、What else …?
What else can I do for you?
What else have you heard?
What else do yo want to know?

3、What kind of …?
What kind of person do you think you are?
What kind of fool do you think I am?
What kind of movie do you like?

What kind of girl do you like?
– I like a loving, considerate, intelligent girl who is confident and knows what she want to do with her life.

4、What do you think … ?
What do you think I should do ?
What do you think you wants?
What do you think America will do to fight the terrorism?

What do you think the chances are of my passing the TOEFL exam?
– I think that your chances are good. You’ve been preparing for a long time and I’ve noticed a big improvment in your spoken English.

5、What would you like to…?
What would you like to know?
What would you like to do next?
What would you like to drink?

6、What do you think of …?
What do you think of China so far?
– Amazing!/Pretty good!

What do you think of her new boyfriend?
– I think he is easy-going, handsome, but stupid.

7、What’s wrong with …?
What’s wrong with George W. Bush?
What’s wrong with this world?
What’s wrong with your phone?

What’s wrong with the computer?
– It’s a cheap piece of junk.

8、What’s your favorite … ?
What’s your favorite food?
What’s your favorite kind of music?

9、What seems to be the problem with … ?
What seems to be the problem with your sister? She looks very upset this morning.

10、What makes/made you … ?
What made you so angry?
What makes you think he did it?
What makes you so motivated?

What makes you say that?
– I’ve been studying English for years. I know what I am talking about.

What makes you do such stupid things?
– I don’t know. I can’t control myself. I don’t want to do stupid things but I just can’t help it.

三、Why …?

1、Why didn’t you …?
Why didn’t you wait for me?
Why didn’t you tell me?
Why didn’t you buy it?

Why didn’t you say something earlier?
Why didn’t you call me?
– I’m terribly sorry. I slipped my mind.

2、Why don’t we just … ?
Why don’t we just have dinner together somewhere this Saturday?

3、Why do you think …?
Why do you think(What makes you think) Guangzhou is a bad place to live?

4、Why do you have to …? (有质问的语气)
Why do you have to tell her the truth?
Why do you have to leave so early?
– I have an early appointment tomorrow morning.

5、Why is it that…?
Why is it that I have had nightmares all these nights?
– Maybe you shouldn’t eat so much chocolate before bedtime.

四、When …?

1、When are you going to …?
When are you going to buy a new house?
When are you going to ask your boss for a raise?

2、When would you like to …?
When would you like to place an order?
– I’m not sure. I still need some time to think it over.

3、When do you want me to …?
When do you want me to have ready for you?
When do you want me to report for work tomorrow?

4、When could you possibly …?
When could you possibly finish this?
When could you possibly let me know the result?
– We will let you know the result as soon as possible.

5、When will it be convenient for you to …?
When will it be convenient for you to arrange an interview for me?
When will it be convenient for you to come to my office?

如发现本站页面被黑,比如:挂载广告、挖矿等恶意代码,请朋友们及时联系我。十分感谢! 图片广告位1 图片广告位2 图片广告位3 商务合作请联系bigwhite.cn AT aliyun.com

欢迎使用邮件订阅我的博客

输入邮箱订阅本站,只要有新文章发布,就会第一时间发送邮件通知你哦!

这里是 Tony Bai的个人Blog,欢迎访问、订阅和留言! 订阅Feed请点击上面图片

如果您觉得这里的文章对您有帮助,请扫描上方二维码进行捐赠 ,加油后的Tony Bai将会为您呈现更多精彩的文章,谢谢!

如果您希望通过微信捐赠,请用微信客户端扫描下方赞赏码:

如果您希望通过比特币或以太币捐赠,可以扫描下方二维码:

比特币:

以太币:

如果您喜欢通过微信浏览本站内容,可以扫描下方二维码,订阅本站官方微信订阅号“iamtonybai”;点击二维码,可直达本人官方微博主页^_^:
本站Powered by Digital Ocean VPS。
选择Digital Ocean VPS主机,即可获得10美元现金充值,可 免费使用两个月哟! 著名主机提供商Linode 10$优惠码:linode10,在 这里注册即可免费获 得。阿里云推荐码: 1WFZ0V立享9折!


View Tony Bai's profile on LinkedIn

文章

评论

  • 正在加载...

分类

标签

归档



View My Stats