1 定义

时间复杂度：指在进行算法分析时，语句总的执行次数 T(n) 是关于问题规模n的函数，进而分析 T(n) 随着 n 的变化情况并确定 T(n) 的数量级的量度，也就是算法的时间量度，记做： T(n)=O(f(n)) 。
它表示随问题规模 n 的增大，算法执行时间的增长率和 f(n) 的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度，其中 f(n) 是问题规模 n 的某个函数。

2 推导大O阶

• 用常数 1 取代运行时间中的所有加法常数。
• 在修改后的运行次数函数中，只保留最高阶项。
• 如果最高阶项存在且不是1，则去除与这个项相乘的常数。
• 最后得到的结果就是大O阶。

3 推导对数阶

看下面的例子
如何求下面程序的时间复杂度？

int i = 1，n=100;
while(i<n){
    i=i*2;
}

我们从代码中可以看到，while循环体中，做的是将最初值 1 通过循环乘以2，来计算出最接近100的值
运行完整段代码，假设需要循环x次，那么计算得到n的公式为： 2 = n
那么根据对数变换公式得到 x = logn
所以，该段程序得时间复杂度为 O(logn)

4 函数调用的时间复杂度分析

4.1 样例一

 看下面代码，执行test方法的时间复杂度是多少？

public void test(int n){
    int i;
    for(i=0;i<n;i++){
        function(i)
    }
}
public void function(int count){
    System.out.println(count);
}

方法function的功能是打印该参数，由代码可知，function函数的时间复杂度是O(1)，在test()方法中，有一个循环体，该循环体的时间复杂度是O(n)，故，执行test方法的时间复杂度为O(n)。

4.2 样例二

如果将上面的function修改成下面这样，那么，执行test方法的时间复杂度是多少？

public void test(int n){
    int i;
    for(i=0;i<n;i++){
        function(i)
    }
}
public void function(int count){
    int j;
    for(j=0;j<count;j++){
          System.out.println(j);
    }
}

分析
当i=0时，j从0计算到0，即function方法中输出了0次
当i=1时，j从0计算到1，即function方法中输出了1次
当i=2时，j从0计算到2，即function方法中输出了2次
……
当i=n时，j从0计算到n，即function方法中输出了n次
所以，总共计算次数为：0+1+2+…+n = （（1+n）/2）n = （n+n）/2
根据前面推导大O阶的方法，没有常数阶，保留最高阶项那么为 n/2，去掉最高阶项相乘的常数，那么剩下的则为 n
所以，该时间复杂度为 0(n)
*

4.3 测一测

自己想一想，下面的代码的时间复杂度又是多少？

public void test(int n){
    int i;
    function(n);
    for(i=0;i<n;i++){
        function(i)
    }
}
public void function(int count){
    int j,x;
    for(j=0;j<count;j++){
        for(x = j;X<count;x++){
          System.out.println("j："+j+"  x："+x);
        }
    }
}

5 常见时间复杂度

常见的时间复杂度所耗费的时间从小到大依次是：
O( 1 ) < O( logn ) < O( n ) < O( nlogn ) < O( n2 ) < O( n3 ) < O( 2n ) < O( n! ) < O( n )

6 最坏与平均

当我们查找一个有n个随机数字数组中的某个数字时，最好的情况是第一个数字就是，那么最好时复杂度为O( 1 )，但也有可能这个数字就在最后一个位置，那么这属于最差情况，最差时时间复杂度为O( n )。平均运行时间时期望的运行时间。
最坏运行时间是一种保证，在应用中，这是一种最重要的需求，通常除非特别指定，我们提到的运行时间都是最坏情况的运行时间。