Chapter 1. 数据结构绪论

概念

• 对数据结构进行结构化定义(D,R)，D 是数据元素的有限集合，R是D上关系的有限集合。

• 抽象数据类型ADT 描述了数据的逻辑结构和抽象运算，通常用三元组（数据对象，数据关系，基本操作集） 表示，从而构建了一个完整的数据结构。

• 连续存储设计时，存储单元的地址一定连续。

连续存储设计就代表物理存储相连。

• 数据逻辑结构与数据物理存储（数据元素本身的形式、相对位置和个数）无关。

• 数据元素是数据的基本单位，数据可由若干个数据元素构成，数据元素可由若干个数据项构成，数据项是数据元素中不可分割的最小可标识单位。

• 算法的五个重要特征：有穷性、确定性、可行性、输入、输出。

考点

• 一个n个元素的数组，左边全是1右边全是0，没有其他元素，则找出1的个数的最佳算法的时间复杂度是 O(log _ 2 n) （二分法）

• 常见结构时间复杂度

O(n^2)

for ( int i = 0; i < n; i++ )
    for ( int j = 0; j < n; j++ )
        k ++;

for ( int i = 0; i < n; i++ )
    for ( int j = 0; j <= i; j++ )
        k ++;

O(log _ a n)

for ( int i = 0; i < n; i++ )
    for ( int j = 0; j < n; j *= a )
        k ++;

O(n)

for ( int i = 0; i < n; i *= 2 )
    for ( int j = 0; j < i; j++ )
        k ++;

i=1,2,4,8,\cdots,2^{k-1} (2 ^{k-1} \le n \le 2^ k)，令 T=1+2+4+8+\cdots+2^{k-1}可得 T \le 2^k \sim O(n)

• 斐波那契数列F(0) = 0,F(1)=1,F(N)=F(N-1)+(N-2)的递归算法时间复杂度为 O(2^n)

F()的参数每加一，递归树（该递归树为二叉树）的树高就加一，结点总数几乎增加一倍。