数据结构 基本概念

什么是数据结构

影响 解决问题方法的效率 的因素：

1. 数据的组织方式
   • 逻辑结构
     1. 线性结构
     2. 树
     3. 图
   • 物理存储结构
2. 空间的利用效率
3. 算法的巧妙程度
   • 霍纳法则

注：集成开发环境可能会有优化机制，测试运行效率时，用gcc 编译更为准确

抽象数据类型(Abstract Data Type)

即，描述数据结构的方法：

• 数据类型
  • 数据对象集
  • 数据集合相关联的操作集
• 抽象：描述数据类型的方法不依赖于具体实现
  • 与存放数据的机器无关
  • 与数据存储的物理结构无关
  • 与实现操作的算法和编程语言均无关

简而言之，只描述数据对象集和相关操作集“是什么”，不涉及“如何做到”的问题

算法定义

• 算法（Algorithm）
  • 有限的指令集
  • 输入可有可无
  • 产生输出
  • 步骤有限
  • 每一条指令必须
    • 明确的目标，无歧义
    • 计算机能处理的范围之内
    • 描述应不依赖于任何一种计算机语言以及具体的实现手段 - 伪码描述

选择排序算法的伪码描述

特点：抽象、不考虑具体实现

void SelectionSort(int List[], int N)
{ /* 将N个证书List[0]...List[N-1]进行非递减排序 */
    for(i = 0; i < N; i ++){
        MinPosition = ScanForMin(List, i ,N - 1);
        //从List[i]到List[N-1]中找到最小元,并将其位置赋给MinPosition
        Swap(List [i], List[MinPosition]);
        //将未排序部分的最小元换到有序部分的最后位置
    }
}

衡量算法的好坏

• 空间复杂度S(n)
• 时间复杂度T(n)
  • 常用复杂度：
    • 最坏情况复杂度$T_{worst}(n)$
    • 平均复杂度$T_{avg}(n)$
    • $T_{avg}(n) \leq T_{worst}(n)$

二分算法分析

//N个递增排序的整数序列List[], 给定待查找整数X, 返回X在List中的下标
//找不到, 返回 -1
void dicotomyFind(int List[], int N, int X)
{
    int M = N/2;
    int min = 0, max = N - 1;
    while(!(List[M] == X))
    {
        if(List[M] > X)
        {
            max = M;
            M /= 2;
        }
        if(List[M] < X)
        {
            min = M;
            M += (N-M)/2 
        }
        
        if(max - min == 0)
        {
            return -1;
        }
    }
    return M;
    
}

时间复杂度：

• 最好：T(N) = O(1)
• 最坏：T(N) = O(logN) 空间复杂度： S(N) = O(1)

复杂度渐进表示

• $T(n)=O(f(n))$表示存在常数$C>0,\ n_0>0,\ n\geq n_0,有\ T(n)\leq C·f(n)$，即最小上界
• $T(n)=\Omega (g(n))$表示存在常数$C>0,\ n_0>0,\ n\geq n_0,有\ T(n)\geq C·f(n)$，即最大下界
• $T(n)=\Theta (h(n))$表示同时有$T(n)=\Omega (g(n))\ 和\ T(n)=O(f(n))$，即上下界相同

常见复杂度大小 $\log{n}<n<n\log{n}<n^2<2^n<n!$

复杂度分析窍门

• 有复杂度：$T_1=O(f_1(n)) 和 T_2(n)=O(f_2(n))$
  • $T_1(n)+T_2(n)=max(\ O(f_1(n)),\ O(f_2(n))\ )$
  • $T_1(n)\times T_2(n)=\ O(f_1(n))\times O(f_2(n))\ )$
• 若T(n) 是关于 n 的k阶多项式, $T(n)=\Theta (n^k)$
• for循环中，$T(n) = 循环次数 \times 循环体复杂度$
• if-else的总体复杂度，取三者最大