数据结构概述 @

数据结构概念 @

数据结构研究数据之间的内在关系，合理组织数据，设计高效的算法，用于解决数学问题。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

数据的逻辑结构和存储结构 @

逻辑结构 @

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

存储结构 @

顺序存储结构，特点是数据存放在连续的内存空间内，可以直接对某个元素进行访问。
链式存储结构，特点是数据存放在不连续的内存空间，无需占用一整块存储空间，但需要对每一个结点附加指针用于存放后继结点的地址，无法直接对某一个元素进行访问。

算法和算法分析 @

算法的定义及特性 @

有穷性，算法必须在一定时间内能执行完。
确定性，算法应不会产生二义性，对于每种情况，应该有确切的操作。
可行性，算法的所有操作应该可以基于基本操作并且在有限时间内完成。
输入，算法有零个或多个输入。
输出，算法有零个或多个输出。

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

正确性，在合理的数据输入下，当数据规模足够大时，都能在有限的时间内得到正确的结果。
可读性，好的算法，应该便于人们理解和相互交流。
健壮性，当输入的数据非法时，好的算法能适当地做出正确反应或者相应地处理。
高效性，高效性包括时间和空间两个方面，时间复杂度与空间复杂度。

算法的时间复杂度 @

衡量算法效率的方法主要分为：

事后统计法，先将算法实现，然后测算其时间和空间开销。
事前分析法，通常采用事前分析估算法，计算复杂度衡量算法的效率。

一个算法的执行时间大致上等于其所有语句执行时间的总和，而语句的执行时间则为该条语句的重复执行次数和执行一次所需时间的乘积。一条语句的重复执行次数称为语句频度。

时间复杂度的定义 @

算法代码举例

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

该算法中所有语句频度之和，是矩阵阶数 n 的函数，用 f(n)表示。

$$ f(n)=2n^3+3n^2+2n+1 $$

对于相对简单的算法，可以直接计算算法所有语句的频度。当问题规模变大时，我们只需要考虑问题规模充分大时，算法中基本语句执行次数在渐近意义下的阶。

$$ \lim_{x \to \infty} f(n)/n^3 = \lim_{x \to \infty} (2n^3 + 3n^2 + 2n + 1)/n^3 = 2 $$

当 n 充分大时，$f(n)$和$n^3$是同阶的，即数量级相同，用”O”表示数量级，记作

$$ T(n)=O(f(n))=O(n^3) $$

一般来说，算法中基本语句重复执行的次数是问题规模 n 的某个函数$f(n)$，算法的时间量度记作$T(n)=O(f(n))$，它表示随问题规模 n 的增大，算法执行时间的增长率和$f(n)$的增长率相同，称作算法的渐近时间复杂度。

数学符号”O”的严格定义为：若$T(n)$和$f(n)$是定义在正整数集合上的两个函数，则$T(n)=O(f(n))$表示存在正的常数 C 和$n_0$,使得当$n>=n_0$时都满足 $0<=T(n)<=C_f(n)$.

算法时间复杂度分析举例 @

基本方法: 找出所有语句中语句频度最大的语句作为基本语句，计算基本语句的频度得到问题规模 n 的某个函数$f(n)$，取其数量级用符号”o”表示。

定理：$f(n) = a_mn^m + a_{m-1}n^{m-1} + … + a_1n + a_0$是一个 m 次多项式，则$T(n)=O(n^m)$

常量阶示例 @

{x++;s=0;}

两条语句频度都为 1，算法时间复杂度为$T(n)=O(1)$

线性阶示例 @

for(i=0;i<n;i++){x++;s=0}

循环体内两条基本语句频度均为$f(n)=n$,所以算法时间复杂度为$T(n)=O(n)$

平方阶示例 @

x=0;y=0;
for(k=1;k<=n;k++)
    x++;
for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
        y++;

循环语句只需考虑循环体中语句的执行次数，其频度为$f(n)=n^2$,所以该算法的时间复杂度为$T(n)=O(n^2)$,称为平方阶。

多数条件下，若干个循环语句时，算法的时间复杂度由最深层循环内基本语句频度决定。

立方阶示例 @

x=1;
for(x=1;i<=n;i++)
    for(j=1;j<=i;j++)
        for(k=1;k<=k;k++)
            x++;

$$ \sum_{i=1}^n\sum_{i=1}^i\sum_{i=1}^j1 = \sum_{i=1}^n\sum_{i=1}^ij = \sum_{i=1}^ni(i+1)/2 = [n(n+1)(2n+1)/6 + n(n+1)/2]/2 $$

该算法时间复杂度为$T(n)=O(n^3)$,称为立方阶。

对数阶示例 @

for(i=1;i<=n;i=i*2){x++;s=0;}

设循环体内两条基本语句的频度为$f(n)$,则有 $2^{f(n)}<=n_1f(n)>=log_2n_1$算法时间复杂度为$T(n)=O(log_2n)$

时间复杂度性能 @

最好时间复杂度：算法计算量可能达到的最小值

最坏时间复杂度：算法计算量可能达到的最大值

平均时间复杂度：算法计算量的加权平均值

空间复杂度 @

输入数据所占的具体存储量取决于问题本身，与算法无关。空间复杂度只需要分析该算法在实现时所需的辅助空间。