当前课程知识点:Data Structures and Algorithm Design Part I >  02.Vector II >  D5.Sorted_Vector.interpolation_search >  02D5-1

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

02D5-1在线视频

下一节:02D5-2

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

02D5-1课程教案、知识点、字幕

同学们好 接下来这节我们来介绍

有序向量查找算法的一个另类的变种

我们称之为插值查找

我们此前所介绍的

斐波那契search或binary search

包括它们的各种版本

对向量只做了一个假定

也就是说其中的元素是单调有序的

但是对于其中元素的分布情况

我们并没有做任何的假设

也就是可以是完全理想任意随机的

但是在某些情况下 也许不是这样

比如说 我们可能不仅知道向量是有序的

而且其中的元素可能是

按照某种先验规律随机分布的

在这里呢 我们考虑一种最常见的随机分布

也就是所谓的均匀独立的随机分布

比如在这样一个从lo

一直到hi的秩的范围之内

所有的元素都互相不影响

也就是所谓各自独立的

然后从取值来看

是均匀的取自于某一个

在这里用横向来表示的区间范围

我们说 如果我们确实知道

诸如此类的规律的话

我们就有可能实现

优于此前那些算法logn的更高的查找效率

具体来讲就是一个小写的o

small o

以这样的一个效率 来完成一次查找

好的 我们来考虑

最终所谓的均匀且独立的随机分布

不难理解

果真是按照这样一个随机分布的话

那么所有的元素在排序之后

也就是组织成一个有序向量之后

必然大体上是按线性增长的趋势分布的

就像这里 从lo开始 最小值

大致是线性的增长到hi 最高值

那么这意味什么呢

意味着对于其中的任何一个潜在元素mi

我们都可以写出这样一个近似的线性等式

也就是说 它们的秩的比

与它们的数值比

二者是近似接近的

这样的话 实际上就给了我们一个启示

也就是说 我们在每次确定mi的时候

既不需要固定的用1/2

也不需要固定的用小写的φ

也就是黄金分割比

甚至不见得要用某一个一般的

我们此前用过的λ

而是可以动态的来猜测这样一个轴点

怎么猜呢?

其实根据的就是这个等式

我们将这个等式稍微整理一下

把mi专门的提到左侧

我们就可以知道

根据lo、hi

以及它们对应的这两个元素的数值

以及每次动态要查找的那个元素的数值e

我们就可以大致的估算或者猜测出了mi

这样的话 如果整个的减而治之的搜索过程

可以认为是一个不断收缩包围圈

逐步收敛的一个过程

那么它将会使得收敛的速度极大的加快

从而更快速的完成我们整个的查找

我们可以来举个例子

正如这个图所画的那样

就是我手头一本英文词典中

abcd 一直到z开头的单词

各自起始的页码

我们说 它大致是1300多页

换而言之 如果它确实

是一个大致平均分布的话

每一个字母大概占50页

所以我们可以大致估算出来

从1到50页 大概是a

50页到100页 大概是b

100页到150页 大概是c 诸如此类

我们可以猜测 其实诸位可以想想

你们在翻阅英文词典的时候

虽然没有去做精确的计算

但是大致你也应该是按这样的来估算的

比如说你去查binary b的话

那么因为它是第二个字母

所以它大概会在整书

从2/26这个位置开始

而s呢 search呢

s是第19个元素 所以大概呢

它会位于19/26的位置

所以你查字典的时候

如果查binary 你绝对不会往后边去查的

而会集中在前面的部分

而s呢 你会更倾向于

在比较靠后的那部分进行查找

我们说 如果你是这么做的话

那么其实你对这种算法的原理

实际上已经很清楚

正因为这种算法在确定切分点

也就是轴点的时候

采用的是近似的插值估算的方法

所以我们也称之为Interpolation Search

插值查找

我们来看一个具体的例子

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

02D5-1笔记与讨论

也许你还感兴趣的课程:

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