当前课程知识点:Data Structures and Algorithm Design Part II >  08.ABST I >  B1.B-Tree.motivation >  08B1-2

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

08B1-2在线视频

下一节:08B1-3

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

08B1-2课程教案、知识点、字幕

实际上 我们不愿意承认 但又不得不接受的一个基本事实是

从某种意义上讲 我们在计算过程中所能够使用和借助的内存

是在日益的变小 而不是如我们直觉那样 变得越来越大

这听起来似乎是个悖论 因为对我们此前所介绍的典型计算模型来说

存储器的大小本身就不是问题 难道不是这样吗

就RAM模型而言 所谓的存储器 无非就是一组寄存器

而且它的数量是无限的

而图灵机的存储器呢 也就是纸带

你应该记得 无论是纸带的长度还是纸带上单元格的数目 都是无限的

然而无论是RAM机还是图灵机 在这一点上都做了过于理想的假设

而在真是的世界中 存储器的容量必然是有限的

而且相对于实际应用的需求 会显得非常非常的有限

事实情况是 在我们的计算系统中

存储容量的增长速度要远远小于应用问题规模的增长速度

为此我们不妨来看这样一组统计数字

按照我们通常对存储容量的规模分级

从千-Kilobyte 到兆-Megabyte 到G-Gigabyte

和T-Terabyte 以及P-Petabyte 诸如此类

而我们人类所拥有的数字化信息的总量

在过去的半个多世纪中 增长速度是惊人的

比如截至2010年总量以及达到Zettabyte

也就是1后面要接21个0

我们知道中国的人口大致是十多亿 也就是10的9次方左右

因此分摊下去 每个人可能都需要一个TB规模的硬盘

请注意 这里我们说的还只是硬盘

而如果考虑内存 这方面的压力就更大了

我们不妨来进一步看一些数字

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

07.Binary Search Tree

-A.introduction

--07A-1

--07A-2

--07A-3

--07A-4

--07A-5

-A.introduction--Homework

-B1.BST : search

--07B1-1

--07B1-2 查找:算法

--07B1-3 查找:理解

--07B1-4 查找:实现

--07B1-5 查找:语义

-B1.BST : search--Homework

-B2.BST : insertion

--07B2-1

--07B2-2

-B2.BST : insertion--Homework

-B3.BST : removal

--07B3-1

--07B3-2

--07B3-3

--07B3-4

-B3.BST : reomval--Homework

-C.balance+equivalence

--07C-1

--07C-2

--07C-3

--07C-4

--07C-5

-C.balance+equivalence--Homework

-D1.AVL : rebalance

--07D1-1

--07D1-2

--07D1-3

--07D1-4

--07D1-5

-D1.AVL : rebalance--Homework

-D2.AVL : insertion

--07D2-1

--07D2-2

--07D2-3

-D2.AVL : insertion--Homework

-D3.AVL : removal

--07D3-1

--07D3-2 删除:双旋

--07D3-3 删除:实现

-D3.AVL : removal--Homework

-D4.AVL : (3+4)-construction

--07D4-1

--07D4-2

--07D4-3

--07D4-4

-D4.AVL : (3+4)-construction--Homework

-Homework

--Homework

08.ABST I

-A1.Splay_Tree.splay1

--08A1-1

--08A1-2

--08A1-3

--08A1-4

--08A1-5

--08A1-6

--08A1-7

--Homework

-A2.Splay_Tree.splay2

--08A2-1

--08A2-2

--08A2-3

--08A2-4

--08A2-5

--08A2-6

--08A2-7

--Homework

-A3.Splay_Tree.implementation

--08A3-1

--08A3-2

--08A3-3

--08A3-4

--08A3-5

--08A3-6

--08A3-7

--Homework

-B1.B-Tree.motivation

--08B1-1

--08B1-2

--08B1-3

--08B1-4

--08B1-5

--08B1-6

--Homework

-B2.B-Tree.structure

--08B2-1

--08B2-2

--08B2-3

--08B2-4

--08B2-5

--08b2-6

--08B2-7

--08B2-8

--Homework

-B3.B-Tree.search

--08B3-1

--08B3-2

--08B3-3

--08B3-4

--08B3-5

--08B3-6

--Homework

08.ABST II

-B4.B-Tree.insertion

--08B4-1

--08B4-2

--08B4-3

--08B4-4

--08B4-5

--Homework

-B5.B-Tree.removal

--08B5-1

--08B5-2

--08B5-3

--08B5-4

--08B5-5

--Homework

-XA1.Red-Black.motivation

--08XA1-1

--08XA1-2

--08XA1-3

--08XA1-4

--Homework

-XA2.Red-Black.structure

--08XA2-1

--08XA2-2

--08XA2-3

--08XA2-4

--08XA2-5

--08XA2-6

--08XA2-7

--Homework

-XA3.Red-Black.insertion

--08XA3-1

--08XA3-2

--08XA3-3

--08XA3-4

--08XA3-5

--08XA3-6

--Homework

-XA4.Red-Black.removal

--08XA4-1

--08XA4-2

--08XA4-3

--08XA4-4

--08XA4-5

--08XA4-6

--08XA4-7

--08XA4-8

--08XA4-9

-Homework

--Homework

09.Dictionary

-B.hashing.principle

--09B-1

--09B-2

--09B-3

--09B-4

--09B-5

--09B-6

--Homework

-C.Hashing.Hash-Function

--09C-1

--09C-2

--09C-3

--09C-4

--09C-5

--09C-6

--09C-7

--09C-8

--09C-9

--09C-A

--09C-B

--Homework

-D1.Hashing.Solving-Collision-1

--09D1-1

--09D1-2

--09D1-3

--09D1-4

--09D1-5

--Homework

-D2.Hashing.Solving-Collision-2

--09D2-1

--09D2-2

--09D2-3

--09D2-4

--09D2-5

--09D2-6

--09D2-7

--09D2-8

--Homework

-E.Bucketsort

--09E-1

--09E-2

--09E-3

--Homework

-Homework

--Homework

10.Priority Queue

-A1.motivation

--10A1-1

--10A1-2

--10A1-3

--Homework

-A2.Basic_Implementations

--10A2-1

--10A2-2

--10A2-3

--Homework

-B1.Complete_Binary_Heap.structure

--10B1-1

--10B1-2

--10B1-3

--10B1-4

--Homework

-B2.Complete_Binary_Heap.insertion

--10B2-1

--10B2-2

--10B2-3

--10B2-4

--Homework

-B3.Complete_Binary_Heap.removal

--10B3-1

--10B3-2

--10B3-3

--10B3-4

--Homework

-B4.Complete_Binary_Heap.heapification

--10B4-1

--10B4-2

--10B4-3

--10B4-4

--10B4-5

--Homework

-C.Heapsort

--10C-1

--10C-2

--10C-3

--10C-4

--Homework

-XA1.Leftist_Heap.structure

--10XA-1

--10XA1-2

--10XA1-3

--10XA1-4

--10XA1-5

--10XA1-6

--Homework

-XA2.Leftist_Heap.merge

--10XA2-1

--10XA2-2

--10XA2-3

--10XA2-4

--Homework

-XA3.Leftist_Heap.insertion+removal

--10XA3-1

--10XA3-2

-Homework

--Homework

11.String I

-A.ADT

--11A-1

--11A-2

--11A-3

--Homework

-B1.Pm

--11B1-1

--11B1-2

--Homework

-B2.brute-force

--11B2-1

--11B2-2

--11B2-3

--11B2-4

--Homework

-C1.Kmp.memorization

--11C1-1

--11C1-2

--11C1-3

--11C1-4

--Homework

-C2.Kmp.lookup-table

--11C2-1

--11C2-2

--11C2-3

--Homework

-C3.Kmp.understanding_next[]

--11C3-1

--11C3-2

--11C3-3

--Homework

-C4.Kmp.constructing_next[]

--11C4-1

--11C4-2

--11C4-3

--Homework

-C5.Kmp.amortization

--11C5-1

--11C5-2

--Homework

-C6.Kmp.improvement

--11C6-1

--11C6-2

--11C6-3

--11C6-4

--11C6-5

11.String II

-D1.BM_BC.begin_with_the_end

--11D1-1

--11D1-2

--11D1-3

--11D1-4

-D2.BM_BC.bad_character

--11D2-1

--11D2-2

-D3.BM_BC.constructing_bc[]

--11D3

-D4.Bm_BC.performance

--11D4-1

--11D4-2

-E1.Bm_GS.good-suffix

--11E1-1

--11E1-2

--11E1-3

-E2.Bm_GS.constructing_gs[]

--11E2

-E3.Bm_GS.performance

--11E3-1

--11E3-2

-F1.KR.fingerprint

--11F1-1

--11F1-2

--11F1-3

-F2.KR.hashing

--11F2-1

--11F2-2

--11F2-3

--11F2-4

-Homework

--Homework

12.Sorting

-A1.Quicksort.algorithm

--12A1-1

--12A1-2

--12A1-3

--12A1-4

-- 12A1-5

--Homework

-A2.Quicksort.performance

--12A2-1

--12A2-2

--12A2-3

--Homework

-A4.Quicksort.Variation

--12A4-1

--12A4-2

--12A4-3

--12A4-4

--12A4-5

-B1.Selection.mode

--12B1-1

--12B1-2

--12B1-3

--12B1-4

--12B1-5

-B2.Selection.Median

--12B3-1

--12B3-2

--12B3-3

--12B3-4

--12B3-5

--12B3-6

--Homework

-C1.Shellsort.Shell's sequence

--12C1-1

--12C1-2

--12C1-3

--12C1-4

--12C1-5

--Homework

-C2.Shellsort.Inversion

--12C2-1

--12C2-2

--12C2-3

-Homework

--Homework

08B1-2笔记与讨论

也许你还感兴趣的课程:

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