第一章-概述

1.1 数据结构的基本概念

什么是数据结构？简单来说，数据结构就是一种关系。

Algorithm + Data Structures = Programs

基本概念和术语

• 数据 Data
• 数据元素 Data Element
• 数据项 Data Item
• 数据对象 Data Object
• 数据类型 Data Type
• 数据结构 Data Structure

数据结构三要素

• 数据的逻辑结构
  • 集合
  • 线性结构
  • 树形结构
  • 图状/网状结构
• 数据的存储结构
  • 顺序存储
    • 连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示
    • C 语言中用数组来实现顺序存储结构
  • 链式存储
    • 用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示
    • C 语言中用指针来实现链式存储结构
  • 索引存储
    • 在存储信息的同时建立索引表（Index）
  • 散列存储 / 哈希存储 Hash
• 数据的运算

1.2 算法的基本概念（书本定义，看下就好）

重要特性

• 有穷性：步骤有穷，执行时间有穷
• 确定性：没有二义性
• 可行性：算法是可执行的
• 输入：有零个或多个输入
• 输出：有一个或多个输出

目标

• 正确性 Correctness
• 可读性 Readability
• 健壮性 Robustness
• 高效性 Efficiency

算法效率的度量

时间复杂度 Time Complex

• 定义：$T(n) = O(f(n))$
• 算法的基本操作执行次数还随问题的 输入数据集的不同而不同
• 最坏时间复杂度
• 平均时间复杂度
• 最好时间复杂度
• 运算规则
• 加法规则
  • $T(n) = T_1(n)+T_2(n) = O(f(n))+O(g(n)) = O(\max(f(n),g(n)))$
• 乘法规则
  • $T(n) = T_1(n)\times T_2(n)=O(f(n))\times O(g(n)) = O(f(n)\times g(n))$
• 常见的渐进时间复杂度为
• $O(1) < O(\log_2n)<O(n)<O(n \log_2n)<O(n^2)<O(n^3)<O(n^k)<O(n!)<O(2^n)$

空间复杂度 Space Complexity

• 定义 $S(n) = O(g(n))$

示例：如何实现数组逆序？ 方案一：空间复杂度为 1 的情况，即$S(n) = O(1)$

for(i = 0; i < n / 2；i++) // 遍历半个数组
{
	t = a[i];              // 临时变量t
	a[i] = a[n-i-1];       // 交换数值
	a[n-i-1] = t;
}

方案二：空间复杂度为 n 的情况，即$S(n) = O(n)$

for(i = 0; i < n； i++)  // 辅助数组b逆序存储a
	b[i] = a[n-i-1];
for(i = 0; i < n, i++)   // 重新赋值给a
	a[i] = b[i];

思考：斐波那契数列，用递归算法和非递归算法的时间复杂度如何？

• 递归算法$O(2^n)$
• 非递归算法$O(n)$