绪论

• 一，相关概念

  • 1，数据（DATA）：各种符号的集合 分为：①数值型数据 实数等 ②非数值型数据 文字图象等
  • 2，数据元素（DATA element）数据的基本单位，在计算机中通常作为一个整体进行考虑和处理，别名为元素，顶点，记录，结点。
  • 3，数据项（DATA item）是构成数据元素的不可分割的最小单位
  • 小结：数据>数据元素>数据项
  • 4，数据对象（DATA object）是性质相同的数据元素的集合，是数据的一个子集

• 二，数据结构

  • 1，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，包括：①逻辑结构 ②存储结构 ③数据运算
  • 2,逻辑结构的种类
    • 划分方法一：
    • 划分方法二：
  • 3，存储结构的分类
    • 1，顺序存储结构： 将数据元素存放在地址连续的存储单元中，其数据间的逻辑关系与物理关系一致。
    • 2，链接存储结构： 将数据元素存放在任意的存储单元中，这组存储单元之间通过链接的方式建立起来。（C语言中用指针实现链式存储结构）
    • 3，索引存储结构： 在存储数据元素的同时，还建立附加的索引表。
    • 4，散列存储结构： 根据元素的关键字直接计算出该元素的存储地址，又称哈希存储结构。
  • 4，数据类型(DATA type)：
    • 是指一个值的集合和定义在这个值集上的一组操作的总称。 作用: 1，数据类型决定了数据对象取值范围 2，数据类型决定了数据对象所能进行的操作
    • 抽象数据类型（Abstract data type,ADT） 定义格式如下：

    ▼
    c
    复制代码
        ADT 抽象数据类型名{
        数据对象：
        数据关系：
        基本操作：
        }ADT 抽象数据类型名
    

    基本操作的定义格式为：

    ▼
    c
    复制代码
        操作名（参数表）
        初始条件：
        操作结果：
    

    • 基本操作的定义格式说明
    • 概念小结

三，算法效率（时间效率和空间效率）

• 1，两种度量方法：
  • ①事后统计方法： 通过设计好的测试程序和数据，利用计算机计时器对不同算法的运行时间进行比较。
  • ②事前分析估算法： 在计算机程序编写前，依据算法所处理的数据规模大小和算法实现所消耗的时间资源、空间资源等，对算法进行估算。
• 2，算法运行时间=一个操作所需时间（假设均为单位时间）×算法中该操作重复执行的次数（语句频度） 算法执行时间约等于语句频度总和
• 3，两个n*n矩阵相乘算法效率分析

  ▼
  c
  复制代码
    for(i=1;i<=n;i++)  //n+1
        for(j=1;j<=n;j++)  //n*(n+1)
            for(k=1;k<=n;k++) //n*n*(n+1)
                c[i][j]+=a[i][k]*b[k][j];//n*n*n
  

  算法耗费时间等于每条语句频度之和 T(n)=（n+1）+n*(n+1)+nn(n+1)+nnn=n^3+3n^2+2n+1
• 4,算法的渐进时间复杂度(O是数量级符号) 简称时间复杂度(T(n)的数量级)
  • 1，忽略低次幂项和最高次幂系数
  • 2，
  • 3，对于复杂的算法，可以分为几个部分，利用加法和乘法法则计算时间复杂度
    • 加法法则 ：T(n)=T1(n)+T2(n) 取两个函数中数量级最大的
    • 乘法法则 ：T(n)=T1(n)*T2(n) 数量级为两个函数的乘积
  • 4，时间复杂度T(n)按数量级递增顺序为 O(1)<O(log2n)<O(n)<O(nlog2n)<O(n^2)<O(n^3)<O(2^n)<O(n!)
• 5，渐进空间复杂度(S(n)的数量级)
  • 1，空间复杂度S(n)分析
    • 1，算法原地工作：算法所需 Workspace 的空间为常量，O(1)
    • 2，递归算法的空间复杂度：递归深度n*每次递归调用所需空间
    • 3，循环工作算法的空间复杂度：循环中使用的变量所占空间
  • 2，空间复杂度S(n)按数量级递增顺序为 O(1)<O(n)<O(n^2)<O(n^3)<O(2^n)<O(n!) 例子：