老王带你理解算法复杂度O(1),O(N),O(N^2)
上圖對應的是算法復雜度的圖片，X軸對應的是n(問題規模)，Y軸對應的是執行的運行時間。
?
我們先從簡單的復雜度解讀O(1)
從上面的圖片我們可以看到O(1)的復雜度是恒定的，一點波瀾都沒有，什么是O(1)呢，就比如你是一個酒店的管理員，你負責管理酒店的鑰匙，你很聰明，你把酒店的100把鑰匙放在了100個格子里面存著，并且把格子從1~100進行了編號，有一天有客人來了，酒店老板說，給我拿10號房間的鑰匙給我，你迅速從10號格子里面拿出鑰匙給老板，速度非常快，這時候你就是一個電腦了，老板跟你說拿幾號房房間的鑰匙，你只需要看一眼就能知道鑰匙在哪里。
存放鑰匙的格子
對應代碼里面可以是這樣的語句
#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++也是一種工具，不要沉迷于一種工具或者“武功”不能自拔，要修煉自己的思維，以無招勝有招，舉個栗子，下雨天的時候，我喜歡開瑪莎拉蒂去上班能擋風遮雨，不下雨的時候我喜歡開我的小毛驢去上班不堵車更快，這樣更方便，各有各的專長和不足，當然對于某些公司把某種編程語言看得非常重要的，我覺得也是值得商榷的。人無完人，我們不可能把所有武功都學會了再去打天下，而是有了自己的專長，對問題有了自己的見解，就可以去做很多事情了。
不足之處，后面再補充
歡迎關注微信公眾號-嵌入式Linux
覺得不錯，請幫忙轉發，點贊，您的每一次支持，我都將銘記于心
?
總結
以上是生活随笔為你收集整理的老王带你理解算法复杂度O(1),O(N),O(N^2)的全部內容，希望文章能夠幫你解決所遇到的問題。
