1. 时间复杂度是什么

时间复杂度表示的是算法执行时间与数据规模变化趋势之间的一种关系。它表示的并不是算法的实际执行时间

2. 时间复杂度的计算

假设有如下的一段代码

int sum(int []array,int n){
    int sum = 0;
    for(int i = 0;i<n;i++){
        sum+=array[i];
    }
    return sum;
}

由于时间复杂度只是估算算法执行时间与数据规模增长之间的一种关系，并不是算法的实际执行时间，我们可以粗略的认为每一行代码的的执行时间都是一样的，记为1个单位，则上面这个函数的执行时间就是

int sum = 0;//执行时间为1

for(int i = 0;i<n;i++){//for循环的执行时间为2n
    sum+array[i];
}

所以T(n)=2n+1;

3. 时间复杂度的表示

时间复杂度用大O来表示，由于时间复杂度表示只是一种变换趋势，所以我们可以忽略常量，低阶知识和高阶指数的系数。上面这个函数的时间复杂度（T(n)=2n+1）可以表示为O(n)。

4. 常见时间复杂度和其计算

常见的时间复杂度有O(1)，O(logn)，O(n)，O(nlogn)，O(n^2)。

4.1 O(1)

O(1)表示常量级时间复杂度，只要代码的执行时间不随n的增大而变化，无论执行多少行代码，则我们都认为这个时间复杂度是常量级的，记为O(1)

int add(int a,int b){
    return a+b;
}

4.2 O(logn)

O(logn)表示对数阶时间复杂度，什么样的代码是对数阶时间复杂度呢？

void log(int n){
    int i = 1;
    while(i<=n){
        i=i*2;
    }
}

这里的while循环会执行多少次呢？while执行的次数也就是当2^k>=n的时候，k=log2(n)(2为底，n的对数)，也就是时间复杂度为O(logn)。当代码为

while(i<=n){
    i=i*3;//或者其它值是，复杂度也是O(logn)
}

根据对数转换公式

log3(n)=log3(2)*log2(n),

而我们计算时间复杂度的时候可以忽略高阶的系数，所以当i= i*3时也是O(logn)

4.3 O(n)

O(n)的示例比较简单

int sum(int []array,int n){
    int sum = 0;
    for(int i = 0;i<n;i++){
        sum+=array[i];
    }
    return sum;
}

4.4 O(nlogn)

O(nlogn)的示例，这里的示例并没有实际意义

int demo(int n){
    for(int i = 0;i<n;i++){
        int k = 1;
        while(k<=n){
              k=k*2;
        }
    }
}

其中

 int k = 1;
 while(k<=n){
      k=k*2;
 }

的时间复杂度为O(logn)，上面已经分析过了，这段代码需要循环执行n边，所以整个这个函数的时间复杂度就是O(nlogn)

4.5 O(n^2)

示例

int demo(int n){
    int num = 0;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            num = num+j;
        }
    }
    return num;
}

两个for循环嵌套，里面的for循环要执行n*n边，所以时间复杂度就是O(n^2)

5. 最好、最差、平均时间复杂度

5.1 什么是最好情况时间复杂度

就是在最理想的情况下，代码执行的时间复杂度

5.2 什么是最坏情况时间复杂

就是在最糟糕的情况下，代码执行的时间复杂度

5.3 什么是平局情况时间复杂度

代码执行在各种可能的情况下的时间复杂的加权平均值，也叫加权平均时间复杂度

三种时间复杂度计算实例

以在数组中查找某个值的位置为例来说明三种时间复杂度的计算

int find(int[]array,int n,int x){
    int pos = -1;
    for(int i = 0;i<n;i++){
        if(array[i]==x){
            pos = i;
            break;
        }
    }
    return pos;
}

最理想的情况，就是要查找的数据就是数组的第一个，for循环只用执行一次就找到了数据对应的位置，这是的复杂度是O(1)，也就是最好时间复杂度是O(1)

最差的情况是，数据不在数组中，遍历完整个数组都没有找到对应的数据。for循环要执行n次，这时的时间复杂度是O(n)，也就是最差时间复杂度为O(n)

平均时间复杂的分析,平均复杂度要更具各种情况的概念和对应情况下的时间复杂度来求平均值

1. 数据在和不在数组中的概率是1:1
2. 数据在[0,n-1]的位置上的概率各是1/n

所以平均时间复杂的计算就是

(1+2+3+……+n)/2n+1/2=(n+1)*n/4n+1/2=(3n+1)/4

根据时间复杂度的大O表示法，去掉系数，常量，所以这个算法的平均时间复杂度就是O(n)