时间复杂度的计算

╰+攻爆jí腚メ 2022-06-15 11:38 212阅读 0赞

如果我们想验证一段代码的效率，一个最直接的办法就是编出来之后运行一下，这个方法称为**事后统计方法**，但是这个方法存在着非常大的弊端，比如我们需要时间编写代码，而代码写完后如果不符合要求需要重新编写；测试的方法会受到硬件和内存占有率的影响等等。所以为了让代码的评估更加规范和科学，我们更多的使用**事前分析估计方法**，即计算一个代码的时间复杂度。  
其实一段代码的时间复杂度计算很容易，它是一种对**计算次数**的统计，它有如下几条规则：  
1.用常数1取代运算次数中所有的加法常数。  
2.只保留最高阶的项。  
3.将最高阶的项前面的系数换成1.  
这个方法被称之为**大O阶方法。**  
我们通过几个例子看一看上述规则到底如何让使用：

##  O ( 1 ) O(1) O(1)复杂度 ##

int  sunm =0,n=100;    //执行1次
    sum= (1+n)*n/2;        //执行1次
    printf("%d",sum);      //执行1次

上面一段代码一共执行3次，但是时间复杂度是 O ( 3 ) O(3) O(3)吗?  
并不是，因为按照规则1，上述代码的时间复杂度应该是 O ( 1 ) O(1) O(1)。  
hash表的查找就是 O ( 1 ) O(1) O(1)的时间复杂度。

##  O ( n ) O(n) O(n)复杂度 ##

int i;                  //执行1次
    for (i = 0;i<n;i++)     //执行n+1次
    {
        
      printf("%d",i);       //执行n次
    }

上面一段代码一共执行 2 n + 2 2n+2 2n\+2次，按照大O阶方法：

2 n + 2 2n+2 2n\+2—> 2 n + 1 2n+1 2n\+1—> 2 n 2n 2n—> n n n

上述代码的时间复杂度应该是 O ( n ) O(n) O(n)。就代表数据量增大几倍，耗时也增大几倍，即时间复杂度是线性的，常见的就是如上述代码所示的遍历算法。

##  O ( n 2 ) O(n^2) O(n2)复杂度 ##

int i,j;                //执行1次
    for (i = 0;i<n;i++)     //执行n+1次
    {
        
    	for (j = 0;j<n;i++) //执行n+1次
    	{
        
    		printf("%d",i);   //执行n*n次
    	}	
    }

上面一段代码一共执行 n 2 + 2 n + 3 n^2+2n+3 n2\+2n\+3次，按照大O阶方法：

n 2 + 2 n + 3 n^2+2n+3 n2\+2n\+3—> n 2 + 2 n + 1 n^2+2n+1 n2\+2n\+1—> n 2 n^2 n2

上述代码的时间复杂度应该是 O ( n 2 ) O(n^2) O(n2)，就代表数据量增大n倍时，耗时增大n的平方倍，这是比线性更高的时间复杂度。比如冒泡排序，就是典型的 O ( n 2 ) O(n^2) O(n2)的算法，对n个数排序，需要扫描 n 2 n^2 n2次。

##  O ( m n ) O(mn) O(mn)复杂度 ##

int i,j;                //执行1次
    for (i = 0;i<n;i++)     //执行n+1次
    {
        
    	for (j = 0;j<m;i++) //执行n+1次
    	{
        
    		printf("%d",i);   //执行n*m次
    	}	
    }

上面一段代码一共执行 m × n + 2 n + 3 m\\times n+2n+3 m×n\+2n\+3次，按照大O阶方法：  
 m × n + 2 n + 3 m\\times n+2n+3 m×n\+2n\+3 —>  m × n + 2 n + 1 m\\times n+2n+1 m×n\+2n\+1 —> m × n m\\times n m×n

上述代码的时间复杂度应该是 O ( m n ) O(mn) O(mn)。 O ( m n ) O(mn) O(mn)复杂度的典型代表是双层循环，当双重训练的次数相同时， O ( m n ) O(mn) O(mn)等效于 O ( n 2 ) O(n^2) O(n2)。

##  O ( l o g n ) O(log^n) O(logn)复杂度 ##

int count = 1;     //执行1次
    while(count<n)   //执行k+1次
    {
        
    	count = count*2;  //执行k次
    }

上面的k如何计算呢？count 每次乘2，直到不再小于n时退出，所以：  
 2 k = n 2^k=n 2k=n，于是 k = l o g 2 n k=log\{\_\{2\}\}^\{n\} k=log2n，所以上述代码共执行 2 l o g 2 n + 2 2log\{\_\{2\}\}^\{n\}+2 2log2n\+2次，按照大O阶方法：

2 l o g 2 n + 2 2log\{\_\{2\}\}^\{n\}+2 2log2n\+2—> 2 l o g 2 n + 1 2log\{\_\{2\}\}^\{n\}+1 2log2n\+1—> 2 l o g 2 n 2log\{\_\{2\}\}^\{n\} 2log2n—> l o g 2 n log\{\_\{2\}\}^\{n\} log2n

一般情况下， l o g 2 n log\{\_\{2\}\}^\{n\} log2n会简写 l o g n log^\{n\} logn（虽然这种写法在数学上是不对的），所以上述代码的时间复杂度应该是 l o g n log^\{n\} logn。当数据增大n倍时，耗时增大 l o g n log^\{n\} logn倍，比如，当数据增大256倍时，耗时只增大8倍，是比线性还要低的时间复杂度）。典型的 l o g n log^\{n\} logn算法就是二分查找，每找一次排除一半的可能，256个数据中查找只要找8次就可以找到目标。

## 总结 ##

最后给出常见的执行次数函数与其对应的时间复杂度：  
![这里写图片描述][format_png]  
常见时间复杂度排序：  
![这里写图片描述][format_png 1]  
常用数据结构，查找，插入，删除复杂度总结：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly96aGFuZ3h1LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70]

[format_png]: /images/20220615/553a0f8283f44408b305481ac34f8122.png
[format_png 1]: /images/20220615/b2b48fb3ece341e6b41b37b964674c9c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly96aGFuZ3h1LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70]: /images/20220615/6d374ba442484aaaaf1482f3c49533c7.png