算法分析

数据结构与算法之间存在着本质联系。在研究某一类型的数据结构时，总要涉及其上施加的计算。
只有通过对所定义运算的研究，才能真正的理解数据结构的定义和作用。

算法要满足的五个特性：

1. 有穷性
2. 确定性
3. 可行性
4. 输入
5. 输出

评价算法优劣的基本标准：

1. 正确性
2. 可读性
3. 健壮性
4. 高效性

1. 时间复杂度

也称渐近时间复杂度，T(n) = O(f(n))

随着问题规模n的增大，算法执行时间和增长速率和f(n)增长率成正比

1.1 总时间的影响因素

• 执行每条语句的耗时（与软硬件有关）
• 每条语句的执行频率（与算法有关）

1.2 计算频度

在计算时间复杂度时，可以省略虽有低次幂和最高次幂的系数

for(int i = 1; i <= n; i++){							//频度为 n+1
	for(int j = 1; j <= n; j++){						//频度为 n*(n+1)
        c[i][j] = 0;									//频度为 n*n
        for(int k = 1; k <= n; k++){					//频度为 n*n*(n+1)
            c[i][j] = c[i][j] + a[i][k] * b[i][j];		//频度为 n*n*n
        }
    }
}														//f(n) = 2*n^3 + 3*n^2 + 2*n + 1，简化为f(n) = n^3

该代码时间复杂度：T(n) = O(n^3)

2. 空间复杂度

空间复杂度主要用来描述某个算法对应的程序对应的程序想在计算机上执行，除了用来存储代码和输入数据的内存空间外，还需要额外的空间

S(n) = O(f(n))

3. 抽象数据类型ADT

ADT是一种编程概念，用于定义数据的类型及其操作，而不涉及具体实现细节。它提供了一种将数据的逻辑表示与物理实现分离的方法，从而使程序更具可维护性和可扩展性

在C语言中，ADT通常通过结构体和函数的结合来实现
结构体用于定义数据的类型
函数用于操作这些数据

痛过这些方，程序员可以隐藏数据的内部结构，仅暴露出操作数据的接口

不理解不影响学习