目錄
何為資料結構？
何為演算法？
演算法效率:
時間復雜度：
概念：
大O的漸進表示法:
推導大O的方法：
空間復雜度：
何為資料結構？
資料結構是計算機存盤、組織資料的方式，資料結構是指相互之間存在一種或多種特定關系的資料元素的集合，
何為演算法？
演算法（Algorithm）是指解題方案的準確而完整的描述，是一系列解決問題的清晰指令，演算法代表著用系統的方法描述解決問題的策略機制，也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出，
演算法效率:
演算法效率分析分為兩種
- 時間效率
- 空間效率
由于當下計算機存盤容量已經達到了很高的程度，所以我們如今已經不需要再特別關注一個演算法的空間復雜度，
百度百科 解釋如下：
https://baike.baidu.com/item/%E7%AE%97%E6%B3%95%E6%95%88%E7%8E%87
時間復雜度：
概念：
在計算機科學中，時間復雜性，又稱時間復雜度，演算法的時間復雜度是一個函式，它定性描述該演算法的運行時間，這是一個代表演算法輸入值的字串的長度的函式，時間復雜度常用大O符號表述，不包括這個函式的低階項和首項系數，使用這種方式時，時間復雜度可被稱為是漸近的，亦即考察輸入值大小趨近無窮時的情況，
！！！！！簡單來說：時間復雜度是指——演算法中基本操作的執行的次數！
！！！！！特別注意：這里指的是次數，不是代碼運行的時間！！！！！
大O的漸進表示法:
void fun1(int N)
{
int count = 0;
for(int i = 0;i < N;++i)
{
for(int j = 0; j< N;++j)
{
++count;
}
}
for(int k = 0; k < 2*N;++k)
{
++count;
}
int M = 10;
while(M--)
{
++count;
}
printf("N = %d,F(N) = %d\n",N,count);
}F(N) = N^2+2*N+10
下面看當N分別為10，100，1000時函式fun1的執行次數
我們可以看出（類似根據求極限的知識...
隨著N的增大，一次項和常數項對于F(N) 的影響越來越小
在實際中，計算時間復雜度是需要大概的執行次數，這里用大O的漸進表示法，
推導大O的方法：
1.1取代常數和系數
2.保留最高階項
通過如上的方法：
第一步：1取代常數和系數
F(N)變為 N^2+N+1
第二步：取最高階數項
F(N)變為 N^2
我們可以求得函式fun1的時間復雜度為 O(N^2)
空間復雜度：
空間復雜度是對一個演算法運行程序中臨時占用存盤空間大小的量度，
！！！！簡單來說，就是變數的個數，
！！！！特別注意：空間復雜度不是指代碼的占記憶體大小，
void BubbleSort(List R,int n)
{
int i,j,temp,end;//定義四個變數
for(i=1;i<=n-1;i++)
{
end=0;
for(j=1;j<=n-i-1;j++)
{
if(R[j].key>R[j+1].key)
{
temp=R[j];
R[j]=R[j+1];
R[j+1]=temp;
end=1;
}
}
if(end==0)
break;
}
}問：上面代碼的空間復雜度是多少？
A:函式中，我們定義了四個變數，F(N) = 4;
用大O的漸進表示法，常數4用1來替換，取最高項
故答案為：O(1)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/290871.html
標籤：其他