数据的专业术语

  1. 数据（Data）是客观事务的符号表示，是所有能输入到计算机中并被计算机程序处理的符号总称

  2. 数据元素（Data Element）是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理

  3. 数据项（Data Item）是组成数据元素的、有独立含义的，不可分割的最小单位

  4. 数据对象（Data Object）是性质相同的数据元素的集合，是数据的一个子集

  5. 数据类型（Data Type）是一个值的集合和定义在这个值集上的一组操作的总称

  6. 抽象数据类型（Abstract Data Type，ADT）： 一般指由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称，具体包括三部分：数据对象、数据对象上关系的集合以及对数据对象的基本操作的集合

数据结构

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

  1. 逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

    1. 集合结构：数据元素之间除了 ”属于同一集合“ 的关系外，无其他关系
    2. 线性结构：数据元素之间存在一对一关系
    3. 树结构：数据元素之间存在一一对多关系
    4. 图状结构或网状结构：数据元素之间存在多对多关系

  2. 非线性结构：

    1. 集合结构
    2. 树结构
      1. 树：具有多个分支的层次结构
      2. 二叉树**：**具有两个分支的层次结构
    3. 图结构
      1. 有向图：一种图结构，边是定点的有序对
      2. 无向图：另一种图结构，边是定点的无序对

  3. 线性结构：

    1. 线性表：经典的线性结构
    2. 栈和队列：数据操作只能在表的一段或者两端进行
    3. 字符串：也是特殊的线性表，其特殊性现在他的数据元素仅有一个字符组成
    4. 数组：是线性表的推广，它的数据元素
    5. 广义表：也是线性表的推广，它的数据元素是一个线性表，但不同构，即或者是单元素，或者是线性表

  4. 存储结构（又称物理结构）：数据对象在计算机中的存储表示。把数据对象存储到计算机时，通常要求既要存储各数据元素的数据，又要存储数据元素之间的逻辑关系，数据元素在计算机内用一个结点表示。

    1. 顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，要求所有的元素依次存放在一片连续的存储空间中
    2. 链式存储结构：无需占用一整块存储空间，但为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后续元素的存储地址

数据的逻辑结构

算法

算法是为了解决某类问题而规定的一个有限长的操作序列

  1. 有穷性：一个算法必须总是在执行有穷步结束，且每一步都必须在有穷时间内完成。
  2. 确定性：对于每种情况下所应执行的操作，在算法中都有确切的规定，不会产生二义性，使算法的执行者或阅读者都能明确其含义及如何执行。
  3. 可行性：算法中所有操作都可以通过已经实现的基本操作运算执行有限次来实现。
  4. 输入：一个算法有零个或多个输入。当用函数描述算法时，输入往往是通过形参表示的。在它们被调用时，从主调函数获的输入值。
  5. 输出：一个算法有一个或者多个输出，它们是算法进行信息加工后得到的结果，无输出的算法没有任何意义。当用函数描述算法时，输出多用返回值或引用类型的形参表示。

评价算法优劣的基本标准

  1. 正确性：在合理的数据输入下，能够在有限的运行时间内得到正确的结果。
  2. 可读性：一个好的算法，首先应便于人们理解和相互交流，其次才是机器可执行性。可读性强的算法有助于人们对算法的理解，而难懂的算法易于隐藏错误，且难于调试和修改。
  3. 健壮性：当输入的数据非法时，好的算法能适当地做出正确反应或进行相应处理，而不会产生一些莫名其妙的输出结果。
  4. 高效性：高效性包括时间和空间两个方面。时间复杂度和空间复杂度是衡量算法的两个主要指标。
    1. 时间高效是指算法设计合理，执行效率高，可以用时间复杂度来度量；
    2. 空间高效是指算法占用存储容量合理，可以用空间复杂度来度量。

时间复杂度

  1. 问题规模：算法求解问题输入量的多少，是问题大小的本质表示，一般用整数 $n$ 表示。
  2. 语句频度：一个语句的重复执行次数。
  3. 最好时间复杂度：算法在最好的情况下的时间复杂度。
  4. 最坏时间复杂度：算法在最坏情况下的时间复杂度。
  5. 平均时间复杂度：算法在所有可能下，按照输入实例以等概率出现时，算法计算量的加权平均值。

一般情况下，算法中基本语句重复执行的次数是问题规模 $n$ 的某个函数 $f(n)$ ，算法的时间复杂度记作 $T(n)=O(f(n))$ ，它表示随问题规模 $n$ 的增大，算法执行时间的增长率和 $f(n)$ 的增长率相同，称为算法的 渐进时间复杂度 ，简称 时间复杂度（Time Complexity）。

时间复杂度：算法在计算机内执行所需运行时间的度量

空间复杂度

空间复杂度：作为算法所需存储空间的度量。它也是问题规模 $n$ 的函数，记作 $S(n)=O(f(n))$