小感想

今天去看了看許多人今年去各個大廠面試的面經(jīng)，確實如大體所說，各大公司越來越注重性能迭代，時代需要數(shù)據(jù)結(jié)構(gòu)與算法這樣的考試。

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

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

時間復(fù)雜度

上一篇搞定了復(fù)雜度的相關(guān)概念，現(xiàn)在就可以直接上陣實戰(zhàn)一手了，為什么要專門搞一個計算實踐，因為不僅是工作，學(xué)校考試啊復(fù)雜度也是和算法直接掛鉤的趁瓷器活沒來趕緊磨磨咱的金剛鉆。

來看第一個：

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

我們求遞歸階乘Func的時間復(fù)雜度，說里面 n 最后要到1，我們可以認(rèn)為遞歸了多少次就他就計算了多少次，我們稍加思索就可以看出他的時間復(fù)雜度是 O(N)。嚴(yán)格來說，遞歸算法怎么計算呢？

是遞歸次數(shù) × 每次遞歸的函數(shù)的次數(shù)

這個每次遞歸函數(shù)的次數(shù)是個什么鬼呢？我們的三目操作符在遞歸中每次會走一次，也就是這個函數(shù)會出現(xiàn)一次，就是所謂的常數(shù)次嘛 O(1)，遞歸了n次，自然就是O(N)了。如果我再在前面加上個 while(n–)，又是一個執(zhí)行n次的循環(huán)，相當(dāng)于是在嵌套循環(huán)了，這是復(fù)雜度就是里外都O(N)，為O(N^2)。

再來

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

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

最后結(jié)果一定會讓n走到 1，這個是總數(shù)的 n ，2^n的 n 只是一個參數(shù)，會發(fā)現(xiàn)每一層都會滿足等比數(shù)列關(guān)系，有 2的（n-1）次方的累加 = 2的n次方 - 1，這里1可以忽略就是2的n次方。

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

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

其實際圖像應(yīng)該是個三角形：

格局繼續(xù)打開

那么如果是2的n次方，那么你將見證一個計算時間復(fù)雜度的極端，要知道算法中二分查找是非?？斓模?0億對象中找一個只需要 log2^1000000000,即30秒左右。

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

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

我們使用遞歸搞斐波那契會有許多重復(fù)，我們改進(jìn)一下：

# 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時發(fā)生越界
{
return Farr;
}
Farr[1] = 1;
}

這個算法就是有前面就能推后面，再看看時間復(fù)雜度是O(N)，這個優(yōu)化簡直就是質(zhì)的優(yōu)化，這個思想就是以空間換時間，開了一個數(shù)組，都用了空間，但是性能更快了。

空間復(fù)雜度

說是空間復(fù)雜度，和空間也不沾關(guān)系，他計算的是大概定義的變量的個數(shù)，實際意義里面就算是結(jié)構(gòu)體大不了你幾十個字節(jié)嘛，也沒必要去整爛活搞幾萬個字節(jié)出來。我小小 8個G，幾十億字節(jié)，你占用我?guī)鬃止?jié)，幾百字節(jié)，幾千字節(jié)我壓根兒不甩你，所以為什么不談空間大小談個數(shù)。

可能如今就只有嵌入式比較介意空間，因為嵌入式通常是在一些設(shè)備上面，舉個栗子就是我們常見的智能居家AI，一個吸塵器機(jī)器人會用到的探測器算法，內(nèi)存條占用多了機(jī)器咋安是吧，不是內(nèi)存貴是空間有限

我們就拿剛剛的階乘來說，從n開始，會建立一個棧幀，每調(diào)用一次遞歸就要創(chuàng)建一個棧幀，每個棧幀里面空間是常數(shù)個，調(diào)用了n次，那么空間復(fù)雜度就是常數(shù)×n為O(N)。

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

以上就是C語言數(shù)據(jù)結(jié)構(gòu)與算法時間空間復(fù)雜度基礎(chǔ)實踐的詳細(xì)內(nèi)容，更多關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)與算法時間空間復(fù)雜度的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論