为什么算法要注意复杂度？
算法的复杂性体现在运行该算法时的计算机所需资源的多少上，计算机资源 最重要的是时间和空间 （即寄存器）资源，因此复杂度分为时间和空间复杂度。
image
基本概念
大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) |
| 5n3+2n2+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]范围内时
image
当n扩大到[0,100)时
image
从图中可以明显的看出
随着n的变大
1、时间复杂度排序 O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)
2、立方阶的复杂度最高；
3、常数阶最小;
下面坐标图均以x[0,5] y[0,15]显示
常数阶
image
当确定会被执行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)
image
中学时候学过的一次函数，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)
image
常用算法或场景：双层遍历、冒泡排序算法、插入排序算法等
简单的双层遍历
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表示法，取最高阶，n2,所以是O(n2)
对数阶O(logn)
image
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)
image
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)
image
典型代表：快速排序、归并排序、堆排序
贴出绘制时间复杂度曲线对比图的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()
网友评论