数据结构

相关概念

抽象数据类型（Abstract Data Type）：一是数据对象集，二是与数据集合相关联的操作集；

类型名称：矩阵
数据对象集：一个m * n的矩阵由 m * n个三元组<a, i, j>构成，其中a是矩阵元素的值，i是元素所在的行号，j是元素所在的列号。

算法（algorithm）
算法是一个有限指令集，它接收一些输入（有些情况下不需要输入），产生输出，并一定在有限步骤之后终止。
算法复杂度：

• 空间复杂度S(n)：根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模n有关。空间复杂度过高的算法可能导致占用内存超限，造成程序非正常中断。
• 时间复杂度T(n)：根据算法写成的程序在执行时耗费时间的长度。这个长度往往也与输入数据的规模n有关。时间复杂度过高的低效算法可能导致我们有生之年都等不到运行结果。

一般而言，在分析算法的效率时，经常关注下面两种复杂度：最坏情况复杂度T_worst(n)和平均复杂度T_avg(n)

渐近表示法：

• T(n) = O(f(n))：表示存在常数C>0, n₀>0，使得当n>=n₀时有T(n)<=C(f(n))。
• T(n) = Ω(g(n))：表示存在常数C>0,n₀>0，使得当n>=n₀时有T(n)>=C(g(n))。
• T(n) = Θ(h(n))：表示同时有T(n)=O(h(n))和T(n)=Ω(h(n))；（线性复杂度）。

注意
O( * ) 和 Ω( * )分别表示上界和下届，但一个函数可以有很多不同的上界和下界。一般地我们希望上下界越接近真实函数越好，所以通常取最小的上界作为O函数，最大的下界作为Ω函数。