Chapter1 数据结构相关概念

数据相关概念：

• 数据：

  • 输入到计算机中被计算机程序识别和处理的符号和集合

• 数据元素：

  • 数据的基本单位，通常作为整体进行考虑和处理。
  • 可由若干数据项构成，数据项为数据元素的不可分割的最小单位。

• 数据对象：

  • 相同性质的数据元素的集合，是数据的一个子集。
    • e.g. 整数数据对象为集合N.

• 数据类型：

  • 一个值的集合和定义在这个值集上的一组操作的总称。

    • e.g. 整型变量 = 某区间整数 + 操作（加、减、乘、除）

  • 原子类型：

    • 其值不可再分的数据类型。

  • 结构类型：

    • 其值可再分为若干成分的数据类型。

• 抽象数据类型（ADT）：(与数据类型实质上一个概念)

  • 一个值域和定义在该值域上的一组操作组成。按值的不同特性分为三类：
    • 原子类型：值不可分解。
      • e.g. 数位为100的整数
    • 固定聚合类型：其值由确定数目的成分按某种结构组成。
      • e.g. 复数由两个实数以确定的次序关系构成。
    • 可变聚合类型：其值由未定数目的成分按某种结构组成
    • 多形数据类型：其值的成分不确定。
      • e.g. 1-6, e1, e2, e3可以是整数或字符或字符串，甚至更复杂的多种成分构成。

  • ADT（Abstract Data Type)：形式定义可由三元组表示

    \[（D,S,P)\]

    其中D是数据对象，S是D上的关系集，P是对D的基本操作集。

      ADT抽象数据类型名{
      	数据对象：<数据对象的定义>
      	数据关系: <数据关系的定义>
      	基本操作：<基本操作的定义>
      }ADT抽象数据类型名
    

    

• 数据结构：

  • 相互之间存在一种或多种特定关系的数据元素的集合。

  • 形式定义：

    \[Data\_structure = (D, S)\]

    其中D是数据元素的有限集，S是D上关系的有限集。

    

  • 逻辑结构：

    • 集合：同属一个集合。
    • 线性结构：一对一。
    • 树形结构：一对多。
    • 图状结构/网状结构：多对多。

  • 存储结构：

    • 顺序存储。
    • 链式存储。
    • 索引存储。
    • 散列存储。

算法相关概念：

• 算法：

  • 对特定问题求解步骤的一种描述。

  • 是指令的有限序列，其中每条指令表示一个或多个操作。

  • 五个重要特性：

    • 有穷性：
      • 有穷步之后结束。
      • 每一步有穷时间完成。
    • 确定性：
      • 每一条指令有确切含义。
      • 算法只有唯一路径，相同输入只能有相同输出。
    • 可行性：
      • 算法中描述的操作可以通过已经实现的节能运算执行有限次实现。
    • 输入：
      • 一个算法有李哥或多个输入，输入取自于某个特定的对象集合。
    • 输出：
      • 一个算法有一个或多个输出，这些输出是同输入有某些特定关系的量。

  • “好”的算法：

    • 正确性：
      • 满足具体问题的需求。
    • 可读性：
    • 健壮性：
      • 处理异常
    • 效率与低存储容量需求：
      • 时间复杂度低
      • 空间复杂度低

• 时间复杂度：

  • 算法中基本运算（最深层循环内的语句）的频度f(n)来分析时间复杂度。

    \[T(n) = O(f(n)) \\ (\lim_{n \to +\infty}\frac{T(n)}{f(n)} = k)\]

  • 加法规则：

    \[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^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)\]

• 空间复杂度：

  • 原地工作：

    • 算法所需辅助空间为常量。