EEPW论坛

存放钥匙的格子

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

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

不足之处，后面再补充