前言

前面我们已经介绍了，研究算法的最终目的是如何花更少的时间，如何占用更少的内存区完成相同的需求，并且也通过案例演示了不同算法之间时间耗费和空间耗费的差异，但我们并不能将时间占用和空间占用量化，因此，接下来我们要学习有关算法时间耗费和算法空间耗费的描述和分析。

• 有关算法的时间耗费分析，我们称之为算法的时间复杂度分析
• 有关算法的空间耗费分析，我们称之为算法的空间复杂度分析

算法的时间复杂度分析

我们要计算算法时间耗费情况，首先我们得度量算法的执行时间，那么如何度量呢？

事后分析估算方法

比较容易想到的方法就是我们把算法执行若干次，然后拿个计时器在旁边计时，这种事后统计的方法看上去的确不错，并且也并非要我们真的拿个计算器在旁边计算，因为计算机都提供了计时的功能。这种统计方法主要是通过设计好的测试程序和测试数据，利用计算机计时器对不同的算法编制的程序的运行时间进行比较，从而确定算法效率的高低，但是这种算法有很大的缺陷：必须依据算法实现编制好的测试程序，通常要花费大量时间和精力，测试完了如果发现测试的非常糟糕的算法，那么之前所做的事情全部白费了并且不同的测试环境（硬件环境）的差别导致测试的结果差异也很大。

public static void main(String[] args){
    long start = System.currentTimeMillis();
    
    int sum = 0;
    int n = 100;
    for(int i=1;i<=n;i++){
        sum += i;
    }
    System.out.println("sum = "+ sum);
    
    long end = System.currentTimeMillis();
    System.out.println(end - start);
}

事前分析估算方法

在计算机程序编写前，依据统计方法对算法进行估算，经过总结，我们发现一个高级语言编写的程序在计算机运行小号的时间取决下列因素：

1. 算法采用的策略和方案；（比如采用A算法还是B算法）
2. 编译产生的代码质量
3. 问题的输入规模（所谓的问题输入规模就是输入量的多少，就好比0-100的和，或者0-1忆之间的和）
4. 机器执行指令的速度

由此可见，剥开这些与计算机硬件、软件有关的因素，一个程序的运行时间依赖于算法的好坏和问题的输入规模，如果算法固定，那么该算法的执行时间就和只和问题的输入规模有关系了。

需求：

​ 计算1到100的和。

第一种解法：

//如果输入量n为1，则需要计算1次；
//如果输入量n为1亿，则需要计算1亿次；
public static void main(String[] args){
    int sum = 0;//执行1次
    int n = 100;//执行1次
    for(int i=1;i<=n;i++){//执行了n+1次
        sum += i;//执行了n次
    }
    System.out.println("sum ="+ sum);
}

第二种解法：

//如果输入量n为1，则需要计算1次；
//如果输入量n为1亿，则需要计算1次；
public static void main(String[] args){
    int sum = 0;//执行1次
    int n = 100;//执行1次
    sum = (n=1)*n/2;//执行1次
     System.out.println("sum ="+ sum);    
}

因此，当输入规模为n时，第一种算法执行了1+1+(n+1)=n=2n+3次；第二种算法执行了1+1+1=3次。如果我们把第一种算法的循环体看做是一个整体，忽略结束条件的判断，那么其实这两个算法运行时间的差距就是n和1的差距。

为什么循环判断在算法1里执行了n+1次，看起来是个不小的数量，但是却可以忽略呢？我们来看下一个例子：

需求：

计算100个1+100个2+100个3+...100个100的结果

算法的空间复杂度分析