01B-3慕课视频播放-Data Structures and Algorithm Design Part I-MOOC慕课视频教程-柠檬大学

在经过了这样一个

等价类的划分之后

我们就可以重新将刚才那样一个

数学的度量的形式进行改写

我们看到这里最大的一个不同就在于

把原来每一个具体的问题实例P

变成了笼统而言的一个规模的度量值

也就是n 也就是说

我们可以把某一个算法

在求解规模为n的不是一个

而是一大类实例的过程中

它们各自所需要的时间成本

笼统记作TA(n)

我们如果暂时把算法固定的话

那么也可以把这个A忽略掉

就直接记作T(n)

很遗憾这样的一个定义

依然不能满足我们实际的需求

不足以支撑我们分析的需要

为什么呢？

我们注意到对于同一问题

即便是规模接近甚至相等的输入实例

计算成本虽然大体是差不多的

但毕竟还是有差异

甚至会有实质性的差异

我们来看这么样一个例子

假设在平面中

随便给定你有限个比如说n个点

那么当然这里的n就是输入规模

我们知道其中的任何三个点

都会定义一个三角形

那么我们这里不妨提出一个问题

就是如何找出其中

面积最小的那个三角形？

如果你不知道技巧的话

不妨采用所谓的蛮力算法

也就是说逐一地去枚举

所有的n中取3的组合

分别的算出它们各自对应的面积

并保留和记录下

最后的整体的最小值

没问题

这个算法的正确性是不言而喻的

但是我们说采用这样

即使是固定的一个算法

对于不同的n个点的组合

有可能运气是不一样的

所需要的成本有很大的区别

比如说我们说在最坏情况下

可能会直到所有的组合都尝试遍后

在最后才会找到

那个最小的三角形

但是反过来也有的时候

你会运气比较好

比如说你在比较早的时候

甚至是一上来所枚举的三个点

你就会发现它们

是不仅像现在这样是近似的共线

而是正好是共线的

这个时候你应该会知道

它的面积是0

而作为面积来说不可能是负值

换而言之

在这个时候其实你已经找到了

这个问题的一个解

也就是说你在这个时候

可以直接返回

报告最小的面积是0

所以我们可以看到

同样规模为n的那些实例

所需要的计算成本是有天壤之别的

当然你还可以举出更多的例子

可能我想有些同学

现在已经想到了我们在前面讲过的

Hailstone的那个例子

它也是这样的情况

好既然这样的话

那么我们又该如何去定义

我们刚才所给出来的这个T(n)呢？

显然我们不能把命运

寄托在最好的情况下

而我们应该更多的

关注一个算法的最坏情况

所以确实如此

如果我们确实像现在大部分的

主要的这种分析的准则所要求的那样

只关心其中的最坏的情况

也就是成本最高的那种情况

那么T(n)的取值应该是

在所有规模为n的问题实例中

将它们的计算成本进行总体的比较

并且取出其中的最大值

这样也就是我们所说的

最坏情况分析的原则

这是首先必须关注的

当然我们也会关注其它的性能

在稍候我们会关注平均性能

分摊性能等等等等

但是我们首当其冲的

确实是最坏的情况

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

01B-3在线视频

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

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

01.Introduction I

01.Introduction II

02.Vector I

02.Vector II

03.List

04.Stack+Queue

05.Binary_Tree

06.Graph

01B-3笔记与讨论

也许你还感兴趣的课程: