本文共 2439 字，大约阅读时间需要 8 分钟。

上图对应的是算法复杂度的图片，X轴对应的是n(问题规模)，Y轴对应的是执行的运行时间。

我们先从简单的复杂度解读O(1)

从上面的图片我们可以看到O(1)的复杂度是恒定的，一点波澜都没有，什么是O(1)呢，就比如你是一个酒店的管理员，你负责管理酒店的钥匙，你很聪明，你把酒店的100把钥匙放在了100个格子里面存着，并且把格子从1~100进行了编号，有一天有客人来了，酒店老板说，给我拿10号房间的钥匙给我，你迅速从10号格子里面拿出钥匙给老板，速度非常快，这时候你就是一个电脑了，老板跟你说拿几号房房间的钥匙，你只需要看一眼就能知道钥匙在哪里。

存放钥匙的格子

对应代码里面可以是这样的语句

#include 
   
    void main(void){    int i = 0;    i = 1;    i = 3;}
   

然后我们说一下O(n)

突然，有一天，你的老板给你说，老王啊，你用100个箱子存100把钥匙，太浪费空间了，你能补能把钥匙上编号一下，然后把钥匙要用绳子穿起来，这样我们可以把这个放箱子的地方再装修一个房间出来。你想了一下，是啊，现在房价这么贵，这样能多赚点钱。

所以你就不能通过上面的方法来找到钥匙了，老板跟你说，老王啊，给我拿45号房间的钥匙出来，你就需要从100个钥匙里面挨个找45个房间的钥匙。

O(n)是随着样本数增加复杂度按指数增加的，如果你的酒店老板把酒店的房间增加到一万个，然后有一天，老外不小心把穿钥匙的绳子弄断了，我了个叉叉叉，这时候老板说，老王快把98号房间的钥匙给我，老王惨爆了~~~我们假设如果老王的老板酒店有两万个房间呢？

for(int i = 1; i<=100: i++){    if(i == 45)          printf("Find it\n");}

继续说一下O(n^2)

随着经济发展越来越好，你的老板把酒店扩大了，有100层每一层有100个房间，当然，你还是你，老王还是老王，工资并没有涨，你因为关注了公众号嵌入式Linux,知道怎么把钥匙排序更好了，你把每一层的钥匙穿在一起，然后一共就有100个用绳子穿起来的钥匙串。

然后老板叫你找钥匙的时候，你先要找到楼层的编号，再对应找到房间的编号，所以大概对应的是这样的代码。

#include 
   
    int main (){    int key;	int array[100][100];		for(int i=1;i<100;i++)		for(int j=1;j<100;j++)			array[i][j] = i*100 +j;	scanf("%d",&key);	for(int i=1;i<100;i++)		for(int j=1;j<100;j++)			if(array[i][j] == key)				printf("FIND KEY\n");    return 0;}
   

这个可以看是O(N^2) +O(N^2) = O(2*N^2) 把常数去掉变成O(N^2)

最后我们解读一下O(log^n)

这个就像是有一百把钥匙，老王在关注公众号后学了不少东西，老王突然觉得，我从头找是不是太慢了，我从中间找，比如我要找到23号的房间钥匙，我从中间切开，找到50编号的位置，然后23在1~50里面，我再把从中间切开变成25，然后23在1~25之间，我再切开变成12.5，然后23在12.5~25之间，依次找下去，直到找到钥匙。这种查找钥匙的方法的复杂度就是O(log^n)

#include 
   
    /** *  折半查找函数 * *  @param arr   数组 *  @param len   数组长度 *  @param value 查找元素 * *  @return 返回查找元素的位置 */int searchItem(int arr[],int len, int value){    int low = 0,high = len-1,mid;    while (low <= high) {        mid = (low + high)/2;        if (value > arr[mid]) {            low = mid+1;        }else if (value < arr[mid]){            high = mid - 1;        }else{            return mid;        }    }    return -1;} int main(int argc, const char * argv[]) {    //数组必须是有序数组   int a[10] = {1,2,31,45,52,62,73,86,90,100};    //查找86元素    int l = searchItem(a,10,86);    printf("loc = %d\n",l);    return 0;}
   

我们知道了O(log^n)可以类推出O(nlog^n)

后话

随着工作时间的推移，发现掌握一种思维远远胜过掌握一种单纯的技能，就比如C语言知识一种工具，C++也是一种工具，不要沉迷于一种工具或者“武功”不能自拔，要修炼自己的思维，以无招胜有招，举个栗子，下雨天的时候，我喜欢开玛莎拉蒂去上班能挡风遮雨，不下雨的时候我喜欢开我的小毛驴去上班不堵车更快，这样更方便，各有各的专长和不足，当然对于某些公司把某种编程语言看得非常重要的，我觉得也是值得商榷的。人无完人，我们不可能把所有武功都学会了再去打天下，而是有了自己的专长，对问题有了自己的见解，就可以去做很多事情了。

不足之处，后面再补充

欢迎关注微信公众号-嵌入式Linux

觉得不错，请帮忙转发，点赞，您的每一次支持，我都将铭记于心

转载地址：https://linus.blog.csdn.net/article/details/85046521 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！