數據結構與算法

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

什么是數據結構？什么是算法？

是數據之間存在一種或多種特定關系的數據元素集合，為編寫出一個“好”的程序，必須分析待處理對象的特性及各處理對象之間存在的關系，這也就是研究數據結構的意義所在為編寫出一個“好”的程序，必須分析待處理對象的特性及各處理對象之間存在的關系這也就是研究數據結構的意義所在

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

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

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列的二維數組。