数据结构、算法

数据结构

• 数据结构的三要素

  • 逻辑结构

    数据中各元素之间的逻辑关系（为如何在计算机中存储做铺垫）

    在这个阶段，我们并不关系这些数据在计算机中是怎么存储的，只是关心数据中各元素之间的关系。也就是说，讨论逻辑结构的时候，和计算无关，只和数据本身有关

    常见的逻辑结构	含义
    集合	所有数据只是被放在一起，彼此之间没有任何联系
    线性结构	数据之间只存在一对一的关系（先后关系）
    树形结构	数据之间存在一对多的关系（如目录结构、家谱图）
    图结构	数据之间是多对多的关系（例如人物关系图）

  • 存储结构（物理结构）

    就是数据在计算机中是如何存储的

    常见的存储结构	含义
    顺序存储	把逻辑上的相邻的元素，存储在物理上也相邻的存储单元中
    链式结构	存储前一个或下一个数据元素的地址，从而实现元素和元素间的关系

• 数据的运算

  • 概念

    数据的运算，包括数据结构的实现，以及基于数据结构上的各种操作

    此时我们已经知道这一堆数据中各个元素之间的关系，也知道这堆数据应该在内存中如何存储。接下来就是要做的就是实现我们的想法，对数据进行各种运算，运算包括

    • 创建数据结构
    • 增加数据
    • 删除数据
    • 查找数据
    • 修改数据
    • 排序数据
    • 输出数据
    • 其他（如 逆序 之类的）

算法、算法效率

• 算法

  算法就是一系列的步骤，将输入的输出转换为期望的结果（算法是可以没有输入的，算法一定是有输出的，不然没有意义）

• 时间效率

  被称为时间复杂度，为算法中的基本操作的执行次数

• 空间效率

  被称作空间复杂度，一般为算法中开辟的内存空间（如变量的个数）

  注：

  • 在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎
  • 经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度
  • 在嵌入式行业，还是比较注重空间利用率的
  • 每个计算机性能不同，使用数学上的极限思想定义复杂度（当N趋近与无穷）

• 算法的好坏评价

  

  算法复杂度（效率从高到低）
  \(O(1)\)
  \(O(logN)\)
  \(O(N)\)
  \(O(NlogN)\)
  \(O(N^2)\)
  \(O(2^N)\)
  \(O(N!)\)

• 计算时间复杂度的分类

  • 最好情况：运行最小次数
  • 最坏情况：运行最大次数
  • 平均情况：任意输入规模期望的运行次数

  注：计算一般用最坏情况

算法竞赛中的时间限制和空间限制

• 限制

  • 时间限制：C++通常设定 1 到 2 秒的时间限制（控制运行次数在 \(10^7\) 到 \(10^8\) 之间）
  • 空间限制：128MB 或 256MB（可以开 \(3\times10^7\) 大小的 int 类型数组，或者 \(5000\times5000\) 大小的二维数组，一般都是够用的）

• 各种数据量下，可选用的算法的时间复杂度（小于 \(10^7\) 即可）