通過上一章，https://www.cnblogs.com/X404/p/11984707.html中可以知道資料結構分為
1.邏輯結構 包含：
1）集合
2）線性結構
3）樹形結構
4)圖結構
2.存盤結構
1）順序存盤
2）鏈式存盤
3）索引存盤
4）散列存盤
以上也是重點需要進行了解的，
廢話不多說，跟著第一章走，演算法的設計應該滿足一下：
1.正確性 ：保證是否正確
2.易讀性：是否簡單易懂
3.健壯性：在輸入非法資料時，是否出錯
4.時空性：分析 時間復雜度 和空間復雜度 提高演算法效率（重點）
選擇最優演算法的2各度量：
時間復雜度：演算法運行時所需要的總步數（從開始運行到打斷點）
空間復雜度：演算法執行時所占的存盤空間（運行后存盤空間的大小）
合理地選擇一種或者幾種操作作為“標準操作”
確定每個演算法執行了多少次標準操作，并將此次數規定位該演算法的計算量
時間復雜度的確定計算量：
演算法的最壞情況時間復雜度：演算法在所有輸入下的計算量的最大值為計算量
(最壞時間復雜度是相當于運動會的接力棒，從開始到結束總共用的時間被稱為最壞時間復雜度）
演算法的平均情況時間復雜度：演算法在所有輸入下的計算量的加權平均值演算法的計算量
(平均情況時間復雜度，仍可以用運動會接力來說，在一段時間內，所平均的值稱為 加權平均）
最壞情況時間復雜度和平均情況復雜度統稱為時間復雜度
最壞情況時間復雜度+加權平均情況復雜度《= 時間復雜度 （最壞和加權是包含在時間復雜度內的）
void max(int a,b,c,d) {a*=d;b*=d,c*=d; if (a>b)x=a; else x=b; if (c>x)x=c; printf("%d\n",x);} /*有時間可以拿筆算一下這個最壞時間復雜度是多少？*/
常見的時間復雜度按數量級遞增排列一次為：
常數 O(1)：無論執行多少行沒有回圈等復雜結構的都是O(1)
int i,j;
i=2;
j=3 i++; j++
i=i+j;
對數階O(long2n):
1 int a; 2 while(a<n){ 3 a=a*2; 4 }
在while回圈里面，每次都將 a 乘以 2，乘完之后，a距離 n 就越來越近了，我們試著求解一下，假設回圈x次之后，a 就大于 2 了，此時這個回圈就退出了，也就是說 2 的 x 次方等于 n，那么 x = log2n
也就是說當回圈 log2n 后代碼就結束，因此這個代碼的時間復雜度為：O(logn)
線性階O(n):
1 int i; 2 for(i=0,i<n,i++){ 3 printf("*******");}
這段代碼，for回圈里面的代碼會執行n遍，因此它消耗的時間是隨著n的變化而變化的，因此這類代碼都可以用O(n)來表示它的時間復雜度，
線性對數階 O(nlong2n):
線性對數階O(nlogN) 其實非常容易理解，將時間復雜度為O(logn)的代碼回圈N遍的話，那么它的時間復雜度就是 n * O(logN)，也就是了O(nlogN)，
1 for(i=1,i<n,i++){ 2 j=1; 3 while(j<n){ 4 j=j*2；}}
平方階O(n2),
多項式階OnC),
指數階O（Cn)
我們可以將時間復雜度幾位輸入資料規模n的函式，若求解問題需要執行n2次操作，則記作O(n2)
時間復雜度與時間的關系
空間復雜度：
是一個演算法在運行程序中臨時占用存盤空間大小的量度，
一個演算法在執行期間所需要的存盤空間量包括以下部分：
程式代碼所占用的空間；
輸入資料所占用的空間；
輔助變數所占用的空間；
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/117882.html
標籤：其他