文章目錄
- 演算法效率
- 大O的漸進表示法規則
- 時間復雜度
- 空間復雜度
演算法效率
演算法效率分析分為兩種：第一種是時間效率，第二種是空間效率，時間效率被稱為時間復雜度，而空間效率被稱作空間復雜度，
時間復雜度主要衡量的是一個演算法的運行速度，而空間復雜度主要衡量一個演算法所需要的額外空間，在計算機發展的早期，計算機的存盤容量很小，所以對空間復雜度很是在乎，但是隨著計算機行業的迅速發展，計算機的存盤容量已經達到了很高的程度，所以我們如今已經不需要再特別關注一個演算法的空間復雜度，這就是為什么我們大多時候聽到的是時間復雜度，而很少聽到空間復雜度的原因，
大O的漸進表示法規則
時間復雜度和空間復雜度一般都使用大O的漸進表示法進行表示，大O的漸進表示法規則如下：
1、所有常數都用常數1表示，
2、只保留最高階項，
3、如果最高階項存在且不是1，則去除與這個項的系數，得到的結果就是大O階，
下面例子中使用大O的漸進表示法的時候會逐步分析，
時間復雜度
時間復雜度的定義：在計算機科學中，演算法的時間復雜度是一個函式，它定量描述了該演算法的運行時間，一個演算法執行所耗費的時間，從理論上說，是不能算出來的，只有你把你的程式放在機器上跑起來，才能知道，但是我們需要每個演算法都上機測驗嗎？是可以都上機測驗，但是這很麻煩，所以才有了時間復雜度這個分析方式，一個演算法所花費的時間與其中陳述句的執行次數成正比例，演算法中的基本操作的執行次數，為演算法的時間復雜度，
實體一：
//計算Func1的時間復雜度
void Func1(int N)
{
int count = 0;
for (int i = 0; i < 2 * N; i++)
{
for (int j = 0; j < 2 * N; j++)
{
count++;
}
}
for (int k = 0; k < 2 * N; k++)
{
count++;
}
}
Func1函式執行了一個嵌套的for回圈（共執行了4 * N2次），又執行了一個單獨的for回圈（共執行了2 * N次），所以Func1函式的時間復雜度為：T(N) = 4 * N2 + 2 * N ，
根據大O的漸進表示法，只保留最高階項（即4 * N2），去除最高項的系數后（即N2），就是最終結果，所以，用大O的漸進表示法表示Func1函式的時間復雜度為：O(N2) ，
實體二：
//計算Func2的時間復雜度
void Func2(int N)
{
int count = 0;
for (int k = 0; k < 100; k++)
{
++count;
}
printf("%d\n", count);
}
Func2函式內部執行了一個for回圈（共100次），Func2函式內陳述句的執行次數不會隨著傳入的變數N的改變而改變，即執行的次數為常數次，Func2函式的時間復雜度為T(N) = 100 ，
根據大O的漸進表示法，所有的常數都用常數1來表示，所以，用大O的漸進表示法表示Func2函式的時間復雜度為：O(1) ，
拓：在刷題時看到題目要求時間復雜度為O(1)，并不是要求函式內部不能含有回圈，而是要求回圈的次數為常數次，
實體三：
//計算二分查找函式的時間復雜度
int BinarySearch(int* a, int N, int x)
{
assert(a);
int begin = 0;
int end = N - 1;
while (begin < end)
{
int mid = begin + ((end - begin) >> 1);
if (x > a[mid])
begin = mid + 1;
else if (x < a[mid])
end = mid - 1;
else
return mid;
}
return -1;
}
計算二分查找函式的時間復雜度，我們需要對代碼進行分析：我們用二分查找法查找資料時，查找一次后可以篩去一半的資料，經過一次次的篩選，最后會使得待查資料只剩一個，那么我們查找的次數就是while回圈執行的次數，
因為資料個數為N，一次查找篩去一半的資料，即還剩N/2個資料，經過一次次的篩選，資料最后剩下1個，那么查找的次數可以理解為N除以若干個2，最后得1，那么while回圈執行的次數就是N除以2的次數，我們只需計算N除以了多少次2最終等于1即可，
我們假設N除以了x個2，最終等于1，那么
最后，兩邊同時取2的對數，得while回圈執行的次數，即x = logN ，所以，用大O的漸進表示法表示二分查找函式的時間復雜度為：O(logN) ，
注：表示時間和空間復雜度時，log表示以2為底的對數，
實體四：
//計算斐波那契函式的時間復雜度
int Fibonacci1(int N)
{
if (N == 0||N == 1)
return 1;
else
return Fibonacci1(N - 1) + Fibonacci1(N - 2);
}
我們知道，使用遞回法求斐波那契數，當我們要求某一個斐波那契數時，需要知道他的前兩個斐波那契數，然后相加得出，那么當我們要知道第N個斐波那契數時，遞回的次數如下圖：
因為右下角的遞回函式會提前結束，所以圖中三角形必定有一塊是沒有資料的，但是當N趨于無窮時，那預設的一小塊便可以忽略不計，這時總共呼叫斐波那契函式的次數為：
這是一個等比數列的求和，最后得出結果為：2N - 1 ，
保留最高階項后，用大O的漸進表示法表示斐波那契函式的時間復雜度為：O(2N) ，
注：遞回演算法的時間復雜度 = 遞回的次數 * 每次遞回函式中的次數，
空間復雜度
空間復雜度是對一個演算法在運行程序中臨時占用存盤空間大小的量度，空間復雜度不是程式占用了多少位元組的空間，因為這個也沒太大意義，所以空間復雜度算的是變數的個數，空間復雜度計算規則基本跟時間復雜度類似，也使用大O漸進表示法，
實體一：
//計算冒泡排序函式的空間復雜度
void BubbleSort(int* a, int N)
{
assert(a);
for (int i = 0; i < N; i++)
{
int exchange = 0;
for (int j = 0; j < N - 1 - i; j++)
{
if (a[j]>a[j + 1])
{
int tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
冒泡排序函式中使用了常數個額外空間（即常數個變數），所以用大O的漸進表示法表示冒泡排序函式的空間復雜度為O(1) ，
實體二：
//計算階乘遞回函式的空間復雜度
long long Factorial(size_t N)
{
return N < 2 ? N : Factorial(N - 1)*N;
}
階乘遞回函式會依次呼叫Factorial(N),Factorial(N-1),…,Factorial(2),Factorial(1)，開辟了N個空間，所以空間復雜度為O(N) ，
注：遞回演算法的空間復雜度通常是遞回的深度（即遞回多少層），
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/273237.html
標籤：其他
上一篇：2021年一戰南大AI上岸經驗貼