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

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

時間復雜度

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

來看第一個：

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

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

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

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

再來

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

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

在這里插入圖片描述

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

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

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

其實際圖像應該是個三角形：

在這里插入圖片描述

格局繼續(xù)打開

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

但是上面的斐波那契運行起來可謂慢的令人發(fā)指，我在之前在學習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時發(fā)生越界
{
return Farr;
}
Farr[1] = 1;
}

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

空間復雜度

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

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

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

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

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

您可能感興趣的文章: