640像素时代,免费体验,完成申请,即有双重礼遇→ 立即申请 ←
电子产品世界 » 论坛首页 » 嵌入式开发 » STM32 » 理解算法复杂度O(1),O(N),O(N^2)

共2条 1/1 1 跳转至

理解算法复杂度O(1),O(N),O(N^2)

高工
2018-12-18 08:13:06    评分


存放钥匙的格子


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


#include <stdio.h>

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 <stdio.h>

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 <stdio.h>

/**

 *  折半查找函数

 *

 *  @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++也是一种工具,不要沉迷于一种工具或者“武功”不能自拔,要修炼自己的思维,以无招胜有招,举个栗子,下雨天的时候,我喜欢开玛莎拉蒂去上班能挡风遮雨,不下雨的时候我喜欢开我的小毛驴去上班不堵车更快,这样更方便,各有各的专长和不足,当然对于某些公司把某种编程语言看得非常重要的,我觉得也是值得商榷的。人无完人,我们不可能把所有武功都学会了再去打天下,而是有了自己的专长,对问题有了自己的见解,就可以去做很多事情了。


不足之处,后面再补充





管理员
2018-12-18 09:11:24    评分
2楼

谢谢楼主分享


共2条 1/1 1 跳转至

回复

匿名不能发帖!请先 [ 登陆 注册 ]