2.0、C语言数据结构——时间复杂度和空间复杂度 (1)

算法效率的度量方法：

事后统计方法：
这种方法主要是通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低

但是这种方法显然是有很大缺项的；
必须依据算法事先编制好测试程序，通常需要花费大量时间和精力，最后发觉测试的是糟糕的算法，那岂不是功亏一篑？
不同的测试环境差别不是一般的大

事前分析估算方法：
在计算机程序编写前，依据统计方法对算法进行估算

经过总结 ->
我们发现一个高级语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：
1、算法采用的策略，方案
2、编译产生的代码质量
3、问题的输入规模
4、机器执行指令的速度

由此可见，抛开这些与计算机硬件、软件有关的因素，一个程序的运行时间依赖于算法的好坏和问题的输入规模。（所谓的问题输入规模是指输入量的多少）

我们再来看看数学家高斯设计的等差数列的算法：

第一种算法【执行了 1+（ n + 1 ）+ n = 2n + 2 次】：


int main() {
    int i = 0;
    int sum = 0;
    int n = 100;   //执行 1 次
    for(i = 0;i <= n;i++) { //执行了n + 1 次
        sum = sum + i; //执行 n 次
    }
    return 0;
}

第二种算法【执行了 1 + 1 = 2 次】：


int main() {
    int sum = 0;
    int n = 100; //执行 1 次
    sum = (1 + n)*n / 2 //执行 1 次
    return 0;
}

如果我们把循环看做一个整体，忽略头尾判断的开销，那么这两个算法其实就是 n 和 1 的差距

再来看一段代码：


int main() {
    int x = 0;
    int sum = 0;
    int i = 0;
    for(i = 0;i < 100;i++) {
        int j = 0;
        for(j = 0;j < 100;j++) {
            x++;
            sum = sum + x; 
        }
    } 
    return 0;
}

这个例子中，循环条件 i 从 1 到 100，每次都要让 j 循环100次，如果非常较真的研究总共精确执行次数，那是非常累的、

另一方面，我们研究算法的复杂度，侧重的是研究算法随着输入规模扩大增长量的一个抽象，而不是精确的定位需要执行多少次，因为如果是这样的话，我们就又得考虑编译器优化等问题~

所以，对于刚才例子的算法，我们可以果断判定需要执行 100^2次

我们不关心编写程序所用的语言是什么，也不关心这些程序将跑在上面样的计算机上，我们只关心它锁实现的算法

这样，不计算那些循环索引的递增和循环终止条件、变量声明带你结果等操作。最终在分析程序的运行时间时，最重要的是把程序看成是独立于程序设计语言的算法或一些列步骤

我们在分析一个算法的运行时间时，重要的是把基本操作的数量和输入模式关联起来