一.简介

​ 时间复杂度可以用来简单的估计代码的运行时间，这对于以后我们评估算法的优劣提供帮助。

二.时间复杂度

基础知识：

  1. 定义：

记T(n)为代码的总运行时间，把每一条语句（全部语句记作n）的执行时间都看做是一样的，记为一个时间单元，

若存在函数 f（n），使得当n趋近于无穷大时，T（n）/ f（n）的极限值为不等于零的常数，则称 f（n）是T（n）的同数量级函数。

记作 T（n）= O（f（n）），称O（f（n）） 为算法的渐进时间复杂度，简称时间复杂度。

  1. 时间复杂度用大写O来表示，所以也被称为大O表示法。

  2. 假设一共有100条语句，那可以认为T(n)=100n；时间复杂度取T(n)的最大阶数: n，即时间复杂度为T(n)=O(n)；

例一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//代码一：
void print(int n)
{
    //i+=i相当于i=i*2,设x次后for循环停止即：2^x=n,即x=log2(n)
    for (int i = 1; i < n; i += i)					//1+2x
    {
        for (int j = 1; j < n; j++)					//x*(1+2n)
        {
            cout << i << '+' << j << "=" << i + j;	//x*n
        }
    }
}

//T(n)=1+2x+x*(1+3n)=1+2log2(n)+log2(n)*(1+3n)=O(nlog2(n))

例二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//代码二：
bool isprime(int n)
{
    
    if (n <= 1)                            	//1
        return false;						//1
    if (n == 2 || n == 3)					//2  	此处n==2，n==3为两个语句，记作2
        return true;						//1
    if (n % 6 != 1 && n % 6 != 5)			//2
        return false;						//1
    //由于满足i*i>n时程序停止，则设x次后停止即：(5+6x)^2=n,即x=(sqrt(n)-5)/6
    for (int i = 5; i * i <= n; i += 6)		//1+2x, 此处i=5运行一次，i*i<=n,i+=6各运行x次
        if (n % i == 0 || n % (i + 2) == 0)	//2*x
            return false;					//1*x
    return true;							//1
}

//T(n)=8+1+2x+x(2+1)+1=5x+10=O(sqrt(n))