算法与数据结构02(基础篇)——时间复杂度简谈

2,497 阅读5分钟

为什么算法要注意复杂度?

算法的复杂性体现在运行该算法时的计算机所需资源的多少上,计算机资源 最重要的是时间和空间 (即寄存器)资源,因此复杂度分为时间和空间复杂度。

基本概念

大O表示法

1. 用常数1取代运行时间中所有常数 3->1 ;例:去定执行3次、6次、2次...标记为 O(1)
2. 在修改运行次数函数中,只保留最高阶项;例:n^3+2n^2+5 标记为 O(n^3)
3. 如果在最高阶存在且不等于1,则去除这个项目相乘的常数。例:2n^3 标记为 O(n^3)

举例说明

原始复杂度 大O表示法
12 O(1)
2n+3 O(n)
3n^2+2n+1 O(n^2)
5log2n+20 O(logn)
2n+3nlog2n+20 O(nlogn)
5n^3+2n^2+n O(n^3)

时间复杂度

时间复杂度大致分为:

1.常数阶O(1)
2.线性阶O(n)
3.平方阶O(n^2)
4.对数阶O(logn) 
5.立方阶O(n^3)
6.nlog阶O(nlogn) 
7.指数阶(咱不在讨论范畴)

下面是通过python绘制的各种复杂度对比曲线,分别是n的范围从[0,5],放大到[0,100)的两张曲线图,
需要这段python曲线绘制代码的同学,请移步文末。

这里暂以n=3的虚线为参考,复杂度过小时,谈论的复杂度的意义就变得很飘渺

当n在[0,5]范围内时

当n扩大到[0,100)时

从图中可以明显的看出

随着n的变大
1、时间复杂度排序 O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)
2、立方阶的复杂度最高;
3、常数阶最小;

下面坐标图均以x[0,5] y[0,15]显示

常数阶

当确定会被执行1次、2次、3次或者很多次,不会因为输入而改变执行次数,执行次数是个常数,抽象认为O(1)。

void testSum1(int n)
{
    int sum = 0;                //执行1次
    sum = (1+n)*n/2;            //执行1次
    printf("testSum1:%d\n",sum);//执行1次
}
void test(int n)
{
    printf("test");//执行1次
}

线性阶O(n)

中学时候学过的一次函数,y = kn + m; 根据大O表示法,k是常数,认为是1, m忽略,所以抽象认为是o(n),函数曲线如上图。

常用算法或场景:遍历、查找等

void testSum2(int n)
{
    for (i = 1; i <= n; i++) { 
        printf("test");          //执行n次
    }
}

执行了 n 次

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

执行了1+n+1 根据大O表示法,上述两段代码的复杂度为O(n)

平方阶O(n^2)

常用算法或场景:双层遍历、冒泡排序算法、插入排序算法等

简单的双层遍历

void add3(int x,int n)
{
    for (int i = 0; i< n; i++) {
        for (int j = 0; j < n ; j++) {
            x=x+1;
        }
    }
}

冒泡排序

/* int arr[]: 排序目标数组; int n: 元素个数 */
void bubbleSort (int arr[], int n) 
{
    int temp;
    int i, j;
    for (i=0; i<n-1; i++) /* 外循环为排序趟数,len个数进行len-1趟 */
        for (j=0; j<n-1-i; j++) { /* 内循环为每趟比较的次数,第i趟比较len-i次 */
            if (arr[j] > arr[j+1]) { /* 相邻元素比较,若逆序则交换(升序为左大于右,降序反之) */
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
}

上述代码的时间复杂度:(n-1) * ... * 3 * 2 * 1 = (n-1)! 大O表示法,取最高阶,n^2,所以是O(n^2)

对数阶O(logn)

void testA(int n)
{
    int count = 1;         //执行1次
    //n = 10
    while (count < n) {
        count = count * 2;
    }
    
}

如何计算上述代码的时间复杂度?
回忆一下高中数学的对数:
2^m = n,
=> m = log2n 2是底,不是2n
放到上述代码中就是:经过m次幂的运算 可以满足n,所以m次就是我们需要的时间复杂度,算法的运算次数,所以求出m就是目的
所以上面代码的时间复杂度:O(1+logn) = O(logn)

立方阶O(n^3)

void testB(int n){
    int sum = 1;                         //执行1次
    for (int i = 0; i < n; i++) {        //执行n次
        for (int j = 0 ; j < n; j++) {   //执行n*n次
            for (int k = 0; k < n; k++) {//执行n*n*n次
                sum = sum * 2;          //执行n*n*n次
            }
        }
    }
}

上述代码可以清晰地看出 三层遍历 每次n次, 所以代码被执行了n * n * n次,故时间复杂度为O(n^3)

nlog阶O(nlogn)

典型代表:快速排序、归并排序、堆排序

贴出绘制时间复杂度曲线对比图的python代码,业余的

copy到jupyter内运行

import matplotlib
import matplotlib.pyplot as plt
import numpy as np
import math
from matplotlib.pyplot import MultipleLocator


plt.figure(figsize=(10,10))

x = np.arange(0.05,400,0.05)
y1 = 1+x*0
y2 = x;
y3 = x*x
y4 = x*x*x
y5 = [math.log(a,2) for a in x]
y6 = [a*math.log(a,2) for a in x]
plt.plot(x, y1)
plt.plot(x, y2)
plt.plot(x, y3)
plt.plot(x, y4)
plt.plot(x, y5)
plt.plot(x, y6)

plt.legend(['O(1)','O(n)','O(n^2)','O(n^3)','O(logn)','O(nlogn)'], loc='upper left')

x_major_locator=MultipleLocator(1)
#把x轴的刻度间隔设置为1,并存在变量里
y_major_locator=MultipleLocator(0.5)
#把y轴的刻度间隔设置为10,并存在变量里
ax=plt.gca()
#ax为两条坐标轴的实例
ax.xaxis.set_major_locator(x_major_locator)
#把x轴的主刻度设置为1的倍数
ax.yaxis.set_major_locator(y_major_locator)
#把y轴的主刻度设置为10的倍数
plt.xlim(0,5)
#把x轴的刻度范围设置为-0.5到11,因为0.5不满一个刻度间隔,所以数字不会显示出来,但是能看到一点空白
plt.ylim(0,5)
#把y轴的刻度范围设置为-5到110,同理,-5不会标出来,但是能看到一点空白

plt.show()