02 向量

ADT vs. Data Structure

ADT = 数据模型 + 定义在该模型上的一组操作 数据结构 = 基于某种特定语言,实现ADT的一整套算法

  • ADT是一种抽象定义,规定的外部的逻辑特性,不考虑时间复杂度,不涉及存储方式

  • 数据结构是具体实现,可以有多种实现方式。是完整的算法,考虑复杂度和具体的存储机制。

数据结构按照逻辑次序的复杂程度,可以分为:

  • 线性结构

  • 半线性结构

  • 非线性结构

线性结构包括了向量和列表(list):

  • 向量:数据项的物理位置和其逻辑次序吻合。此时的逻辑次序也称为秩(rank)

  • 列表:逻辑上相邻的数据项在物理上未必相邻。

2.1 从数组到向量

数组的元素一般是基本类型。向量是数组的抽象与泛华,其元素可以是复杂类型。

数组是用下标访问。向量是循秩访问

2.4 动态空间管理

两种扩容策略的比较

我们不断的向vector中插入n个数。共执行n次操作。

递增策略

倍增策略

累积增容时间

O(n^2)

O(n)

分摊增容时间

O(n)

O(1)

装填因子

约等于100%

>50%

可以直观的想象一下,我们插入n个数。递增策略(假设按2递增)在每2,4,6,8,10...时,都要扩容一次。而倍增策略则在2,4,8,16时才扩容。

但是倍增策略的装填因子小于递增策略,可以看做是以空间换时间。(且换取的时间远远大于空间的成本)

平均分析 vs 分摊分析

平均分析(average/expected complexity)

  • 即求数据结构各种操作的加权成本

  • 把操作独立的来看,割裂了各种操作之间关联

分摊分析(amortized complexity)

  • 对数据结构连续的实施足够多的操作,所需总体成本分摊至单次操作

  • 从总体出发,能更好的评判数据结构和算法的真实性能

2.5 常规向量

有序向量和无序向量

  • 无序向量:元素支持比对操作,即比较是否相等

  • 有序向量:元素支持比较操作,即比较大小(且确实是排好序的)

有序性及其甄别

  • 有序向量中,任意一对相邻元素顺序

  • 无序向量中,存在一对相邻元素逆序

向量的逆序程度可以用向量逆序对的数量来度量。

2.6 有序向量

有序向量的查找

我们规定search返回 小于等于e,且秩最大的元素。这样的语义规定可以方便的配合其他算法使用。

二分查找版本A(即最常规的二分查找)

  • 减而治之,实际上是分成三部分(建议都用小于号)

    • e < x

    • x < e

    • e = x

没有查找到返回-1,这个版本不符合我们的语义规定

  • 查找长度:即关键码的比较次数

fib查找

二分查找版本A向左转时,之比较了一次。向右转时,要比较两次。即向右转的成本比向左转的成本高。

fib查找的O(logn)的常系数要小于二分查找版本A。