C語言資料結構與演演算法時間空間複雜度基礎實踐

小感想

今天去看了看許多人今年去各個大廠面試的面經，確實如大體所說，各大公司越來越注重效能迭代，時代需要資料結構與演演算法這樣的考試。

一個公司的成本主要來自於人力成本，但是上了規模寫核心程式碼的人少了，成本就會來自於機器，資源，時間，搶佔到這些就相當於無時無刻在減少客戶流失。所以同樣一段程式碼給兩個人寫，甲拿 8000，乙拿 25000，但是後者效率提高了50%，而這50%帶來的收益遠遠超過了（25000-8000），這就是為什麼許多大廠要給出如此吸引人的高薪資來招賢納士。

說回來要省時間省資源就無法規避掉演演算法，所以說總會有那麼一天咱還是得要直面恐懼。

時間複雜度

上一篇搞定了複雜度的相關概念，現在就可以直接上陣實戰一手了，為什麼要專門搞一個計算實踐，因為不僅是工作，學校考試啊複雜度也是和演演算法直接掛鉤的趁瓷器活沒來趕緊磨磨咱的金剛鑽。

來看第一個：

long Func(n)
{
return n<2?n:Func(n-1)*n ;
}

我們求遞迴階乘Func的時間複雜度，說裡面 n 最後要到1，我們可以認為遞迴了多少次就他就計算了多少次，我們稍加思索就可以看出他的時間複雜度是 O(N)。嚴格來說，遞迴演演算法怎麼計算呢？

是遞迴次數 × 每次遞迴的函數的次數

這個每次遞迴函數的次數是個什麼鬼呢？我們的三目操作符在遞迴中每次會走一次，也就是這個函數會出現一次，就是所謂的常數次嘛 O(1)，遞迴了n次，自然就是O(N)了。如果我再在前面加上個 while(n–)，又是一個執行n次的迴圈，相當於是在巢狀迴圈了，這是複雜度就是裡外都O(N)，為O(N^2)。

再來

long Func(n)
{
return n<2?n:Func(n-1)+(n-2); 
}

這是斐波那契的遞迴數列，乍一看和上面的階乘沒太大區別，還是在算他遞迴了多少次，但是這下可沒那麼好算了捏。這時我們可以拿起筆畫一畫多半就有個譜了

最後結果一定會讓n走到 1，這個是總數的 n ，2^n的 n 只是一個引數，會發現每一層都會滿足等比數列關係，有 2的（n-1）次方的累加 = 2的n次方 - 1，這裡1可以忽略就是2的n次方。

但是！完了嗎？我們格局開啟

這裡的-1,是要每一層都是滿的才滿足，但是實際上不滿，我們 n，n-1，n-2……最後是1沒毛病；我們到其他路線上，n-2，n-3，n-4……壓根兒到不了最後一行，在他頭上提早結束，後面的同理，也就是說我們整個流程圖在後面會有一大坨空白部分，沒有呼叫次數捏。但是！就算缺吧，這些漏網份子依然相對於整體而言非常的小，影響不大，估算角度他依然是2^n。

其實際影象應該是個三角形：

格局繼續開啟

那麼如果是2的n次方，那麼你將見證一個計算時間複雜度的極端，要知道演演算法中二分查詢是非常快的，要在10億物件中找一個只需要 log2^1000000000,即30秒左右。

但是上面的斐波那契執行起來可謂慢的令人髮指，我在之前在學習C語言遞迴時就在vs2019上試過，當n = 10時，1000次，小兒科秒出；n = 30時，十億次，很快啊，看來CPU是有備而來，n = 50時，可以說久了去了,整個程式沒有卡死勝似卡死。

看看咱CPU執行速度是多少赫茲可以換算執行速度，一般民用設定高一點點的能達到一秒十億次計算，別看n只是漲了一點點，電腦壽命夠長就給n整個80，你的壽命夠長就可以給n整個100。

我們使用遞迴搞斐波那契會有許多重複，我們改進一下：

# include<stdio.h>
# include<malloc.h>
long long*Func(n)
{
long long* Farr= malloc(sizeof(long long)*(n+1));
Farr[0] = 0;
if(n==0)  // 防止n=0時發生越界
{
return Farr;
}
Farr[1] = 1;
}

這個演演算法就是有前面就能推後面，再看看時間複雜度是O(N)，這個優化簡直就是質的優化，這個思想就是以空間換時間，開了一個陣列，都用了空間，但是效能更快了。

空間複雜度

說是空間複雜度，和空間也不沾關係，他計算的是大概定義的變數的個數，實際意義裡面就算是結構體大不了你幾十個位元組嘛，也沒必要去整爛活搞幾萬個位元組出來。我小小 8個G，幾十億位元組，你佔用我幾位元組，幾百位元組，幾千位元組我壓根兒不甩你，所以為什麼不談空間大小談個數。

可能如今就只有嵌入式比較介意空間，因為嵌入式通常是在一些裝置上面，舉個栗子就是我們常見的智慧居家AI，一個吸塵器機器人會用到的探測器演演算法，記憶體條佔用多了機器咋安是吧，不是記憶體貴是空間有限

我們就拿剛剛的階乘來說，從n開始，會建立一個棧幀，每呼叫一次遞迴就要建立一個棧幀，每個棧幀裡面空間是常數個，呼叫了n次，那麼空間複雜度就是常數×n為O(N)。

今天就先到這裡吧，摸了家人們。

以上就是C語言資料結構與演演算法時間空間複雜度基礎實踐的詳細內容，更多關於C語言資料結構與演演算法時間空間複雜度的資料請關注it145.com其它相關文章！