C語言資料結構與演演算法之時間空間複雜度入門

2022-02-15 16:00:24

資料結構與演演算法

終於開始搞這塊難啃的骨頭了，走上這條漫漫長路之前要明白：

什麼是資料結構？什麼是演演算法？

是資料之間存在一種或多種特定關係的資料元素集合，為編寫出一個“好”的程式，必須分析待處理物件的特性及各處理物件之間存在的關係，這也就是研究資料結構的意義所在為編寫出一個“好”的程式，必須分析待處理物件的特性及各處理物件之間存在的關係這也就是研究資料結構的意義所在

演演算法是解決特定問題求解步驟的描述，在計算機中表現為指令的有限序列，並且每條指令表示一個或多個操作

拋開上面的學術性口水話，簡單來說就是:

1.資料結構是計算機儲存，組織資料的方式

2.演演算法是一系列規定的計算步驟，為了實現的特定的計算目的而應用

給個更直觀的檢視就是：演演算法+資料結構就等於程式，資料結構可以理解為實現一個程式的基本單位，演演算法可以看作一個加工過程。

比如我去從一個很大的陣列裡面提取某個特定的物件，我們既可以老老實實從頭到尾遍歷查詢，也就是所謂的暴力搜尋，工程量隨著陣列的容量增大而增大；我們也可以巧奪智取，用二分查詢讓我們工作事半功倍。

分析維度

在知道基本概念後，我們說在拿到一個演演算法後，我們怎麼去看他的好壞？或者給你多個演演算法，他們都實現同一個功能，我們怎麼去判斷他的優缺點去取捨呢？正常情況下，我們會選擇把這個程式碼放在某個環境下執行比較時間，但這個做法有一個致命的缺點，在我們不同機器上，會有不同的結果，在好的機器上，執行時間會很短，但是在比較差一點的主機上，就稍有遜色，這樣一來就有失公平。

大O的漸進表示法

不要直接計算時間，，我們需要去計算一個漸進的時間複雜度，也就是所謂的Big O （大O表示法），他其實本質上實在求一個量級（時間）在增加時的一個變化趨勢

時間複雜度公式：T（n）=O(f(n))

T（n）：時間頻度（執行次數）
n ：問題規模；
f（n）：T(n)的同數量級函數；
O ：代表正比例關係；
Ｏ(f(n)）：即演演算法的漸進時間複雜度

常數階

我們的算加法的完整過程：

int main()
{
int a = 1;
int b = 1;
int sum = a+b;
printf("%d",sum);
}

我們每走一步就會執行一次，上面的程式碼我就執行了四次；那麼如果我把他的sum部分重複執行數十次數百次數千次，但他本質上和執行四次沒有區別，執行時間是恆定的，這個層面上，他的時間複雜度就是O（1）（常數階）。

不管這個常數是多少，4或∞，都不能寫成O(4)、O(∞)，都要寫成O(1)

線性階

我們給出一個 for loop

for(int a = 1;a<=n;a++)
{
 a++;
}

分析線性階時會比常數階更復雜因為要分析他的迴圈結構，上面的程式碼限制再++，總共執行3次，包括常數階的賦值就是O（3n+1），在我的n足夠大時他會無限接近於無窮，這時的+1就會沒有意義。

這時就順理成章，巢狀迴圈我們也就可以理解了，兩層 for 就是O（n2)，三層就是O（n2）for 下面加一個雙層for迴圈就是O（n+n2）……這裡面就包含了**平方階**；此時我O(n)的效率就比O（n2）高。

對數階

我們再給出一個while loop

int n = 0;
while(n<100000)
{
n*=2;
}

我們要看執行次數就要看多少步才能走出迴圈，就意味著要乘 x 個2能>=10000，則表示為 2^x =100000，假設為亂數 a，則 x= log 2 ^a，
複雜度為O（logn）

除了上面三種之外還有其他的複雜度

從常數階到階乘是越來越複雜，我們看一下直觀資料：

這裡橫軸是輸入（input）量級，縱軸是消耗時間也就是時間複雜度，也就是有個很直觀的資訊：演演算法複雜度越高，需要的時間越長，到後面就直接指數級增長。

其他時間複雜度指標

雖然有下面這些種吧，但我們主要會把重心放在 O 上，畢竟它是最常用的指標。

空間複雜度

空間複雜度是指記憶體空間增長的趨勢，相對就容易理解一些，O（1）就是相當於單次賦值，而 O（n）相當於賦值n次，可以把他想成一個大小為 n 的陣列，複雜度越高需要分配的空間就越多；同理，O（n^2）就可以想成一個n行n列的二維陣列。

今天就到這裡吧，摸了家人們，更多關於C語言資料結構與演演算法時間空間複雜度的資料請關注it145.com其它相關文章！