@toc
學習了資料結構第一章時間空間複雜度計算，這篇應該近幾周的最後一次更新了開學得軍訓兩周，兩周之後再繼續學習。
資料結構 (data structure)是計算機存儲、組織資料的方式，指互相之間存在一種或多種特定關系的資料元素的集合。
算法(algorithm):就是定義良好的計算過程，他取一個或一組的值為輸入，并産生出一個或一組值作為輸出。簡單 來說算法就是一系列的計算步驟，用來将輸入資料轉化成輸出結果。
算法效率分析分為兩種：第一種是時間效率，第二種是空間效率。時間效率被稱為時間複雜度，而空間效率被稱作空間複雜度。 時間複雜度主要衡量的是一個算法的運作速度，而空間複雜度主要衡量一個算法所需要的額外空間，在計算機發展的早期，計算機的存儲容量很小。是以對空間複雜度很是在乎。但是經過計算機行業的迅速發展，計算機的存儲容量已經達到了很高的程度。是以我們如今已經不需要再特别關注一個算法的空間複雜度
時間複雜度的定義：在計算機科學中，算法的時間複雜度是一個函數，它定量描述了該算法的運作時間。一個算法執行所耗費的時間，從理論上說，是不能算出來的，隻有你把你的程式放在機器上跑起來，才能知道。但是我們需要每個算法都上機測試嗎？是可以都上機測試，但是這很麻煩，是以才有了時間複雜度這個分析方式。一個算法所花費的時間與其中語句的執行次數成正比例，算法中的基本操作的執行次數，為算法的時間複雜度。
空間複雜度是對一個算法在運作過程中臨時占用存儲空間大小的量度。空間複雜度不是程式占用了多少bytes的空間，因為這個也沒太大意義，是以空間複雜度算的是變量的個數。空間複雜度計算規則基本跟實踐複雜度類似，也使用大o漸進表示法。
因為在不同的硬體電路中，同一個程式編譯花費的時間是不同的，是以，計算時間複雜度不能直接計算程式運作花費的時間，而算法中的基本操作的執行次數，就是算法的時間複雜度。<code>時間複雜度用大寫字母o加上( )表示，即o( );</code>
<code>推導大o階方法：</code>
<code>用常數1取代運作時間中的所有加法常數。</code>
<code>在修改後的運作次數函數中，隻保留最高階項。</code>
<code>如果最高階項存在且不是1，則去除與這個項目相乘的常數。得到的結果就是大o階。</code>
請計算下列代碼的時間複雜度：
func1執行的基本操作次數 ：
$$
f(n)=n^2+2*n+10
n = 10 f(n) = 130
n = 100 f(n) = 10210
n = 1000 f(n) = 1002010
通過上面我們會發現<code>大o的漸進表示法去掉了那些對結果影響不大的項</code>，簡潔明了的表示出了執行次數。
實際中我們計算時間複雜度時，<code>我們其實并不一定要計算精确的執行次數，而隻需要大概執行次數，那麼這裡我們使用大o的漸進表示法。</code>
是以這個程式的時間複雜度可以表示為：
o(n^2)
另外有些算法的時間複雜度存在最好、平均和最壞情況：
最壞情況：任意輸入規模的最大運作次數(上界) 平均情況：任意輸入規模的期望運作次數 最好情況：任意輸入規模的最小運作次數(下界) 例如：在一個長度為n數組中搜尋一個資料x 最好情況：1次找到 最壞情況：n次找到 平均情況：n/2次找到 <code>在實際中一般情況關注的是算法的最壞運作情況，是以數組中搜尋資料時間複雜度為o(n)</code>
題目1：
此時算法的執行次數是2n+10次，通過推導大o的漸進表示法 <code>時間複雜度是o(n)</code>
題目2
此時算法的執行次數是m+n次，有兩個未知數，時間複雜度是o(m+n);
如果給了條件：
m遠大于n，時間複雜度是o(m);
m，n大小差不多，時間複雜度是o(m)或o(n);
題目3：
執行次數為100次 為是常數，是以<code>時間複雜度為o( 1 )</code>
題目4
sttrchr是在一個字元串中查找一個字元，查找次數最好o(1)，最壞o(2)，根據大o的漸進表示法是以<code>時間複雜度為o(n)</code>
題目5
因為比較的數字是n-1,n-2,n-3…3,2,1反過來就是1,2，3，…，n-3，n-2,n-1規律就是一個等差數列根據等差數列求和公式(n^2+n)/2，
那麼根據<code>大o的漸進表示法就是o(n ^ 2)</code>
題目6
在一個有序的數組中一直二分直到找到要找的那個數字,那麼n/2/2/2…=1,那麼就可以變換為2^x=n,那麼x就是log以2為底，n的次方，<code>時間複雜度就是</code>
o(log2^n)
題目7
這題n是不是要遞歸到1才停止遞歸，那麼就是遞歸n次。
這個題目求n階層,那麼算法的執行次數就是n，<code>時間複雜度就是o(n)</code>
<code>遞歸複雜度=遞歸次數*每次遞歸函數次數</code>
題目8：
大o的漸進表示法<code>時間複雜度是o(2^n)</code>
畫圖分析：
非遞歸算法 o(n)=n
空間複雜度是對一個算法在運作過程中臨時占用存儲空間大小的量度，即在函數中有幾個臨時變量
題目1
使用了5個( 常數 )個額外空間，是以<code>空間複雜度為 o(1)</code>
這裡動态開辟了n+1個空間，是以<code>空間複雜度是o(n)。</code>
裡遞歸每次調用一次函數，就會開辟一次棧幀，每個棧幀使用了常數個空間，是以<code>空間複雜度為o(n)</code>