时间复杂度的意义

时间复杂度是对算法好坏衡量的一个标准。试想同样一个功能a算法实现只要1000ms内存只有5MB，而b算法需要2000ms甚至更多，内存需要50MB甚至跟多
衡量代码的好坏包括两个非常重要的指标：

1. 运行时间
2. 占用空间

由于代码的运行环境和规模影响，绝对时间是无法猜测出来的但是可以根据代码的执行次数来预顾出时间

基本操作执行次数

一： 例如有10斤大米，每2天吃1斤，那么吃掉10斤大米需要几天
答案是 2x10 = 20天
如果大米的重量是N斤那么吃掉所有的大米就需要 2 x n = 2n 天
所以相对时间就是 T(n) = 2n

二： 例如有20斤大米，每3天吃掉剩余大米的一半第一天吃10斤，第二天吃5斤，第三天吃2.5斤，那么需要多少天
答案是 3 x log20 = 3 x 4 + 1天 = 13天
如果大米的重量是N斤那么需要 3 x logn
相对时间就是 T(n) = 3logn

三：例如有5斤大米和一个鸡腿，2天吃掉一个鸡腿那么吃掉整个鸡腿所需时间？
答案是：2天 因为只是说鸡腿跟大米没有关系
如果大米重量是n，无论大米多重吃鸡腿的实际仍然是2天
T(n) = 2

四：例如有10斤大米，吃掉第一个1斤需要1天，第二个1斤需要两天 第三个1斤需要三天... 那么吃掉所有大米时间是多少呢？
答案是： (1+2+3+4...+7+8+9+10) = 55
如果大米重量是N那么时间为 (1+2+3...+n-2+n-1+n) = (1 + n) * (n*0.5) = 0.5 * n^2 + 0.5 * n
T(n) = 0.5^2 + 0.5n

这一思想同样适用于对程序基本操作执行次数的统计

一： T(n) = 2n

void eat1(int n){
    for(int i=0; i<n; i++){;
        System.out.println("等待一天");
        System.out.println("等待一天");
        System.out.println("吃一斤米");
    }

二： T(n) = 3logn

///以2为底 n的幂
void eat2(int n){
   for(int i=1; i<n; i*=2){
       System.out.println("等待一天");
       System.out.println("等待一天");
       System.out.println("吃一半米");
   }
}

三：T(n) = 2

void eat3(int n){
   System.out.println("等待一天");
   System.out.println("吃一个鸡腿");
}

四：T(n) = 0.5n^2 + 0.5n

void eat4(int n){
   for(int i=0; i<n; i++){
       for(int j=0; j<i; j++){
           System.out.println("等待一天");
       }
       System.out.println("吃一斤米");
   }
}

时间复杂度分析

有了基本操作执行次数的函数 T（n），是否就可以分析和比较一段代码的运行时间了呢？还是有一定的困难。
比如算法A的相对时间是T（n）= 100n，算法B的相对时间是T（n）= 5n^2，这两个到底谁的运行时间更长一些？这就要看n的取值了。
所以，这时候有了渐进时间复杂度（asymptotic time complectiy）的概念，官方的定义如下：
若存在函数 f（n），使得当n趋近于无穷大时，T（n）/ f（n）的极限值为不等于零的常数，则称 f（n）是T（n）的同数量级函数。
记作 T（n）= O（f（n）），称O（f（n）） 为算法的渐进时间复杂度，简称时间复杂度。
渐进时间复杂度用大写O来表示，所以也被称为大O表示法。

推导时间复杂度

如果运行时间是常数量级，用常数1表示；
只保留时间函数中的最高阶项；
如果最高阶项存在，则省去最高阶项前面的系数。

一：T(n) = 2n
最高项为2n 则省出系数3 转化为时间复杂度为 T(n) = O(n)

二：T(n) = 3logn
最高项为3logn 则省出系数3 转化为时间复杂度为 T(n) = O(logn)

三：T（n） = 2
最高项为2 则省出系数2 转化为时间复杂度为 T(n) = O(1)

四：T（n） = 0.5n^2 + 0.5n
最高阶项为0.5n^2，省去系数0.5，转化的时间复杂度为T（n） = O（n^2）

这四种复杂度时间耗时为
O(1) < O(logn) < O(n) < O(n^2)
除了上述的四个场景，还有许多不同形式的时间复杂度，比如：
O（nlogn）, O（n^3）, O（m*n），O（2^n），O（n！）

时间复杂度的巨大差异

例子
算法A的相对时间规模是T（n）= 100n，时间复杂度是O(n)
算法B的相对时间规模是T（n）= 5n^{2，时间复杂度是O(n}2)

两种时间规模的差异.png

从表格中可以看出，当n的值很小的时候，算法A的运行用时要远大于算法B；当n的值达到1000左右，算法A和算法B的运行时间已经接近；当n的值越来越大，达到十万、百万时，算法A的优势开始显现，算法B则越来越慢，差距越来越明显。
这就是不同时间复杂度带来的差距。