基础概念

数据结构

基础概念

• 数据：信息的载体，能够被计算机识别、存储、加工、处理。

• 数据元素：数据的基本单位，数据元素可由若干个数据项构成。

• 数据对象：数据的子集，具有相同性质的数据元素的集合。

• 数据结构：由数据元素和结构（元素之间的相互关系）组成。 $$ Data_Stryctrues = (D, S) $$

• 逻辑结构：集合、线性结构、树形结构（非线性）、图形结构（非线性）。

• 关系：<a_i, a_j> 或 （a_i, a_j） ------前驱或弧尾<=>后续或弧头

数据的物理结构

逻辑结构在存储器中的映象

• 数据元素的存储（图就是存每个顶点的信息）
• 关系的存储（图就是存各个顶点的关系，比如邻接矩阵的方式存储）

关系的描述方式

• 顺序存储结构
• 链式存储结构

算法

基础概念

• 算法：对特定问题求解步骤的一种描述，是指令的有限序列（有顺序）。
• 特性：有穷性、确定性、可行性、输入、输出。

注：输入可以为空，但没有输出的算法是毫无意义的。

• 程序与算法：
  • 程序不一定满足有穷性（比如操作系统）。
  • 程序的指令必须是计算机可执行的，算法的指令无此限制。
  • 如果用机器可执行的语言书写算法，那么算法就是程序。
• 算法设计的原则
  • 正确性：应当满足具体问题的要求。
  • 健壮性：处理异常。
  • 可读性
  • 执行算法所消耗的时间（量化）
  • 执行算法所消耗的存储空间（量化）

时间复杂度

简要

算法所消耗的时间：算法中所有语句执行时间（语句的频度--语句重复执行的次数）之和

for i in range(n):  #n+1
    for j in range(n):  #n*(n+1)
        C[i][j] = 0  #n*n
        for k in range(n):  #n*n*(n+1)
            C[i][j] = C[i][j] + B[i][j]  #n*n*n

时间复杂度 $$ T(n):2n^3+3n^2+2n+1 $$

渐进时间复杂度 $$ O(n^3) $$

注：都是求最坏情况下的原操作句执行次数，平均情况也是一种不错的衡量假设

常见算法时间复杂度

$$ O(c) < O(\log_2n) < O(n) < O(n\log_2n) < O(n^2) < O(2^n) < O(n!) <O(n^3)<O(n^n) $$

算法的时间复杂度不仅是问题规模n的函数，还与所处理的数据集有关，所以我们需全面考虑它在最坏情况、最好情况、平均情况下的代价

空间复杂度

• 输入数据所占空间
• 程序本身所占空间
• 辅助变量所占空间

辅助变量所占空间是我们经常需要考虑的

注：时间复杂度与空间复杂度我们更倾向于考虑时间复杂度，现在的内存没有几十年前珍贵，但时间能带给用户更好的体验，这是其中一个原因，当然，具体情况具体分析