当前课程知识点:Data Structures and Algorithm Design Part I >  01.Introduction II >  F.Dynamic_Programming >  01XC-3

返回《Data Structures and Algorithm Design Part I》慕课在线视频课程列表

01XC-3在线视频

下一节:01XC-4

返回《Data Structures and Algorithm Design Part I》慕课在线视频列表

01XC-3课程教案、知识点、字幕

没错 我们这里又碰到了指数

不同的是 我们这次要对这个指数

来做一次准确地估计

反过来验证一下

我们刚才实际

运行这段代码的效果

为什么是那样

我们来看一下 在这里

作为封底估算的一种基本技能

也要求大家能够记下

这样一个大概的估计式

具体地讲 也就是Φ的指数

也就是36次幂

和2的25次幂是相当的

怎么来记忆这个呢?

我们说 很好记

36是6的平方

而25是5的平方

好记吧

基于这样的一个大致估计

我们就可以来估计一下

Fibonacci数的第43项

刚才我们已经明显地

感觉到延迟的那一项

所需要计算的成本

那么 根据这个来估算

大致就等于2的30次方

2的30次方是多少呢?

等于2的10次方的3次方

而2的10次方呢

是等于10的3次方

当然是约等于

所以当然就是10的9次方了

也就是说我们的计算工作量

大概可以用10的9次方条

基本操作指令来度量

而前面刚刚讲过

10的9次方就是现在主流的计算机

一个gigahertz主频的CPU

在一秒钟之内

大致能够吞吐的计算量

这也就是为什么

当我们的计算大致接近43

甚至更大的时候

我们会明显地感觉到延迟

为了更好的理解指数

对于我们实际的计算

延迟的那种感受

我们再来推算一下

这里用到另一个近似式

也就是Φ的5次方大致就是10

因此我们可以来估算一下

Φ的67次方

也就是对应我们算出

Fibonacci数的第67项

大概需要多少时间

我们来看 它的计算成本

大概是10的14方条基本指令

为了吞吐或者执行这么多条指令

我们需要多少时间呢?

在同样的9次方的主频下

我们做一次除法 或者说14减9

应该会得到10的5次方 这么多秒

10的5次方是多少?

大家应该已经学会“封底估算”

应该有这种直觉了

前面也讲过 10的5次方

大致就是一天

换而言之 刚才那段程序

如果我不中止的话

它在算出第67项之前

我们也许应该先下课

大家回去休息一晚上

第二天 我们再来看它运行的结果

一天 仅仅对于第67项

这个是很可怕的一件事

当然 为了再进一步地 有所感觉

我们不妨来 再估算一下

多少呢?我们来看一下

为了算出Fibonacci数的第92项

我们大致需要多少时间

同样地 根据刚才那个估算

我们需要的指令的数目

大概是10的19次方

同样地 10的19次方

除以10的9次方

19减9 我们会得到

10的10次方秒

10的10次方秒是多少?

我们此前刚刚介绍过

它就对应于

我们俗称的叫三生三世

或者准确地讲就是三个世纪

三个century

大家可以看到这里确实

远远地超过了我们的直觉

利用这个算法

即便是算出不超过一百项

我们就需要用我们一生

都难以承受之久的等待

这说明什么呢?

说明这个算法不好

从严格的意义上讲

它甚至不是一个算法

虽然从表面上看

它还像那么一回事

Data Structures and Algorithm Design Part I课程列表:

01.Introduction I

-A.Computation

--01A-1

--01A-2

--01A-3

--01A-4

--01A-5

--演示

--01A-6

--(a)计算--作业

-B.Computational_Models

--01B-1

--01B-2

--01B-3

--01B-4

--01B-5

--01B-6

--01B-7

--01B-8

-B.Computational_Models--Homework

-C.Big_o

--01C-1

--01C-2

--01C-3

--01C-4

--01C-5

--01C-6

--01C-7

-C.Big_o--Homework

01.Introduction II

-D.Algorithm_analysis

--01D-1

--01D-2

--01D-3

--01D-4

--01D-5

--01D-6

--01D-7

-D.Algorithm_analysis--Homework

-E.Iteration+Recursion

--01E-1

--01E-2

--01E-3

--01E-4

--01E-5

--01E-6

--01E-7

--01E-8

--01E-09

-E.Iteration+Recursion--Homework

-F.Dynamic_Programming

--01XC-1

--01XC-2

--01XC-3

--01XC-4

--01XC-5

--01XC-6

-- 演示

--01XC-7

--01XC-8

--01XC-9

--01XC-A

-F.Dynamic_Programming--Homework

-Homework

02.Vector I

-A.Interface+Implementation

--02A-1

--02A-2

--02A-3

--02A-4

--02A-5

-A.Interface+Implementation--Homework

-B.extendable_vector

--02B-1

--02B-2

--02B-3

--02B-4

--02B-5

-B.extendable_vector--Homework

-C.unsorted_Vector

--02C-1

--02C-2

--02C-3

--02C-4

--02C-5

--02C-6

--02C-7

--02C-8

-C.unsorted_Vector--Homework

-D1.Sorted_Vector.uniquify

--02D1-1

--02D1-2

--02D1-3

--02D1-4

--02D1-5

-D1.Sorted_Vector.uniquify--Homework

-D2.Sorted_Vector.binary_search

--02D2-1

--02D2-2

--02D2-3

--02D2-4

--02D2-5

--02D2-6

--02D2-7

-D2.Sorted_Vector.binary_search--Homework

02.Vector II

-D3.Sorted_Vector.fibonaccian_search

--02D3-1

--02D3-2

--02D3-3

--02D3-4

-D3.Sorted_Vector.fibonaccian_search--Homework

-D4.Sorted_Vector.binary_search_optimized

--02D4-1

--02D4-2

--02D4-3

--02D4-4

--02D4-5

-D4.Sorted_Vector.binary_search_optimized--Homework

-D5.Sorted_Vector.interpolation_search

--02D5-1

--02D5-2

--02D5-3

--02D5-4

--02D5-5

-D5.Sorted_Vector.interpolation_search--Homework

-E.Bubblesort

--02 E-1

--02E-2

--02E-3

--02E-4

--02E-5

-E.Bubblesort--Homework

-F.Mergesort

--02F-1

--02F-2

--02F-3

--02F-4

--02F-5

--02F-6

-F.Mergesort-Homework

-Homework

03.List

-A.interface+Implementation

--03A-1

--03A-2

--03A-3

--03A-4

-A.interface+Implementation--Homework

-B.Unsorted_list

--03B-1

--03B-2

--03B-3

--03B-4

--03B-5

-B.Unsorted_list--Homewrok

-C.Sorted_list

--03C-1

--03C-2

--03C-3

-C.Sorted_list--Homewrok

-D.Selectionsort

--03D-1

--03D-2

--03D-3

--03D-4

--03D-5

--03D-6

-D.Selectionsort--Homework

-E.Insertionsort

--03E-1

--03E-2

--03E-3

--03E-4

--03E-5

--03E-6

--03E-7

--03E-8

-E.Insertionsort--Homework

-(xd):LightHouse

--03XD

-Homework

04.Stack+Queue

-A.stack-ADT+implementation

--04A-1

--04A-2

--04A-3

-A.stack-ADT+implementation--Homework

-C1.stack-App-conversion

--04C1-1

--04C1-2

--04C1-3

-C1.stack-App-conversion--Homework

-C2.stack-App-parentheses

--04C2-1

--04C2-2

--04C2-3

--04C2-4

--04C2-5

--04C2-6

-C2.stack-App-parentheses--Homewrok

-C3.stack-App-permutation

--04C3-1

--04C3-2

--04C3-3

--04C3-4

--04C3-5

-C3.stack-App-permutation--Homework

-C4.stack-App-infix

--04C4-1

--04C4-2

--04C4-3

--04C4-4

--04C4-5

--04C4−6A

--04C4−6B

--04C4−6C

--04C4-6D

-C4.stack-App-infix--Homework

-C5.stack-App-rpn

--04C5-1

--04C5-2

--04C5-3

--04C5-4

-C5.stack-App-rpn--Homework

-D.Queue-ADT+implementation

--04D-1

--04D-2

--04D-3

-Homework

05.Binary_Tree

-A.Tree

--05A-1

--05A-2

--05A-3

--05A-4

--05A-5

--05A-6

--05A-7

-A.Tree--Homework

-B.Representation

--05B-1

--05B-2

--05B-3

--05B-4

--05B-5

-B.Representation--Homework

-C.Binary_Tree

--05C-1

--05C-2

--05C-3

-C.Binary_Tree--Homework

-D.Implementation

--05D-1

--05D-2

--05D-3

--05D-4

--05D-5

-D.Implementation--Homework

-E1.Preorder

--05E1-1

--05E1-2

--05E1-3

--05E1-4

--05E1-5

--05E1-6

--05E1-7

--05E1-8

--05E1-9

-E1.Preorder--Homework

-E2.Inorder

--05E2-1

--05E2-2

--05E2-3

--05E2-4

--05E2-5

--05E2-6

--05E2-7

-E2.Inorder--Homework

-E4.LevelOrder

--05E4-1

--05E4-2

--05E4-3

-E4.LevelOrder--Homework

-E5.reconstruction

--05E5-1

--05E5-2

--05E5-3

-E5.reconstruction--Homework

-Homework

06.Graph

-A.Introduction

--06A-1

--06A-2

--06A-3

-A.Introduction--Homework

-B1.Adjacency_Matrix

--06B1-1

--06B1-2

--06B1-3

--06B1-4

--06B1-5

--06B1-6

--06B1-7

--06B1-8

--06B1-9

-B1.Adjacency_Matrix--Homework

-C.BFS

--06C-1

--06C-2

--06C-3

--06C-4

--06C-5

--06C-6

--06C-7

--06C-8

-C.BFS--Homework

-D.DFS

--06D-1

--06D-2

--06D-3

--06D-4

--06D-5

--06D-6

--06D-7

-D.DFS--Homework

-Homework

01XC-3笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。