C語言數據結構與算法時間空間復雜度實例分析

這篇文章主要介紹“C語言數據結構與算法時間空間復雜度實例分析”的相關知識，小編通過實際案例向大家展示操作過程，操作方法簡單快捷，實用性強，希望這篇“C語言數據結構與算法時間空間復雜度實例分析”文章能幫助大家解決問題。

時間復雜度

來看第一個：

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語言數據結構與算法時間空間復雜度實例分析”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識，可以關注億速云行業資訊頻道，小編每天都會為大家更新不同的知識點。