??歡迎光顧我的homepage

前言

? ? ? ? 算法就是定義良好的計算過程，它取一個活一組的值輸入，并產生出一個或一組值作為輸出。簡單來說，算法就是一系列的計算步驟，用來將輸入數據轉化成輸出結果。

一、算法效率

? ? ? ? 如何去衡量一個算法的好壞？

? ? ? ? 算法在編寫成可執行程序后，運行時消耗時間和空間資源。因此，一般從時間和空間兩個維度來衡量，即時間復雜度和空間復雜度。

時間復雜度和空間復雜度

? ? ? ? 時間復雜度主要衡量一個算法的運行快慢，而空間復雜度主要衡量一個算法運行時所需要的額外空間。? ? ? ?

? ? ? ? 在計算機發展的早期，計算機的存儲容量很小。所以對復雜度很是在乎。但是計算機行業的迅速發展，計算機存儲容量已經達到很高的程度，所以我們并不用特別關注算法的空間復雜度

二、時間復雜度

? ? ? ? 時間復雜度是指算法在執行過程中，所需要的時間資源和問題規模之間的關系，主要衡量算法的運行效率，用來估算算法在不同規模下的運行時間

????????時間復雜度用大O的漸進表示法來表示

2.1時間復雜度的計算

? ? ? ? 算法的時間復雜度是一個函數式T(N)，它定量描述了該算法的運行時間。

實際上，我們計算時間復雜度時，計算主要涉及到以下幾個方面

基本操作次數： 時間復雜度的計算通常關注算法中執行的基本操作次數，例如賦值操作、比較操作、算術運算等。通常將這些操作的數量與輸入規模相關聯。

循環結構： 算法包含循環結構，需要考慮循環的迭代次數以及每次迭代中的基本操作數量。

遞歸調用： 對于遞歸算法，需要考慮遞歸的深度以及每次遞歸調用的時間復雜度。通常使用遞歸方程（遞歸關系式）來表示遞歸算法的時間復雜度。

分支結構： 如果算法包含分支結構，需要考慮每個分支的執行次數以及分支中的基本操作數量。

輸入規模： 時間復雜度的計算通常與輸入規模有關。輸入規模表示算法操作的數據量或問題的大小，通常用符號n表示。

? ? ? ? 說白了，算法復雜度其實就是計算基本操作的執行次數
看一個案例，來計算時間復雜度

void Func1(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;}
}

這里Func函數基礎語句執行次數 T(N)=N^2+2N+10

用大O的漸進表示法表示就成了 O(N^2)

大O的漸進表示法

1 . 時間復雜度的函數式T(N)中，只保留最高階項，去掉那些低階項

2 . 如果最高項存在且不是1，則去掉這個項的常數系數

3 . T（N）中如果沒有N的相關項，只要常數項，用常數1來取代所有加法常數

2.2、時間復雜度計算實例

2.2.1、示例一

void Func1(int N)
{int count = 0;for (int k = 0; k < 2 * N; ++k){++count;}int M = 10;while (M--){++count;}printf("%d\n", count);
}

Func1函數基本操作次數

???????? T（N）= 2N+10

? ? ? ? 大O漸進表示法? Func1的時間復雜度為：O(N)

2.2.2、示例二

void Func2(int N, int M)
{int count = 0;for (int k = 0; k < M; ++k){++count;}for (int k = 0; k < N; ++k){++count;}printf("%d\n", count);
}

Func1函數基本操作次數

????????T（N）= M+N

? ? ? ? 因為這里無法確定M和N的大小，所以有大O漸進表示法 就為：O(M+N)

2.2.3、示例三

void Func3(int N)
{int count = 0;for (int k = 0; k < 100; ++k){++count;}printf("%d\n", count);
}

Func3函數的基本操作次數

? ? ? ? T（N）=100

? ? ? ? 用大O漸進表示法 表示 O(1)

2.2.4、示例四

const char* strchr(const char* str, int character)
{const char* p_begin = s;while (*p_begin != character){if (*p_begin == '\0')return NULL;p_begin++;}return p_begin;
}

這里計算strchr函數的基本操作次數? ? ? ?

? ? ? ? 如果查找的字符在字符串的第一個位置（靠前的位置）則T（N）= 1

? ? ? ? 如果查找的字符在字符串最后 則T（N）=? N

? ? ? ? 如果查找的字符在字符串中間位置 則T（N）= N/2

這樣用大O漸進表示法就要三種情況

情況一： O(1)????????情況二： O(N)????????情況三： O(N)

這里我們就會發現，有些算法的時間復雜度存在多種情況

? ? ? ? 最好情況 ： 任意出入規模的最小運行次數（下界）

? ? ? ? 最壞情況 ： 任意輸入規模的最大運行次數（上界）

? ? ? ? 平均情況： 任意輸入規模的期望運行次數

大O漸進表示法在實際情況中一般關注的是算法的上界，也就是最壞運行情況。

所以這里strchr函數的時間復雜度為：O（N）

2.2.5、示例五

void BubbleSort(int* a, int n)
{assert(a);for (size_t end = n; end > 0; --end){int exchange = 0;for (size_t i = 1; i < end; ++i){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;}}if (exchange == 0)break;}
}

冒泡排序的時間復雜度

? ? ? ? 如果數組有序為升序，則T(N) = N （最好情況）

? ? ? ? 如果數組有序為降序，則T(N) = (N*(N+1))/2 （最壞情況）

因此BubbleSort的時間復雜度為 O(N^2)

2.2.6、示例六

void func4(int n)
{int cnt = 1;while (cnt < n){cnt *= 2;}
}

Func4函數

? ? ? ? n=2，執行次數為1

? ? ? ? n=4，執行次數為2

? ? ? ? n=16，執行次數為4

? ? ? ? 當執行次數為x時，n=2^x

? ? ? ? 所以執行次數 x=

所以時間復雜度為：

這里也可以寫成log n

????????當N接近無窮大時，底數的大小對結果影響不大。因此，一般情況下不管底數為多少都可以省略不寫，寫成log n

2.2.7、示例七

long long Fac(size_t N)
{if (0 == N)return 1;return Fac(N - 1) * N;
}

這里每一次調用Fac函數的時間復雜度為O(1)

? ? ? ? 而一共有n次遞歸，所以階乘遞歸的時間復雜度為O（N）

三、空間復雜度

? ? ? ? 空間復雜度也是一個數學表達式，是對一個算法在運行過程中因為算法的需要額外臨時開辟的空間

????????空間復雜度表示程序占用了多少bytes的空間，因為常規情況下每個對象大小 差異不會很大，所以空間復雜度計算的是變量的個數

? ? ? ? 空間復雜度也使用大O漸進表示法

? ? ? ? 這里函數運行時所需要的棧空間（存儲參數，局部變量。一些寄存器信息等）在編譯期間已經確定好了，空間復雜度主要通過函數在運行時顯示申請的額外空間來確定

空間復雜度計算

示例一

void BubbleSort(int* a, int n)
{assert(a);for (size_t end = n; end > 0; --end){int exchange = 0;for (size_t i = 1; i < end; ++i){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;}}if (exchange == 0)break;}
}

函數棧幀在編譯期間已經確定好了，只需關注函數在運行時額外申請的空間

BubbleSort額外申請的空間有exchange等有限個局部變量，使用了常數個額外的空間

? ? ? ? 因此時間復雜度為：O(1）

示例二

long long Fac(size_t N)
{if (N == 0)return 1;return Fac(N - 1) * N;
}

Fac遞歸調用了N次，額外開辟了N個函數棧幀，每個棧幀使用了常數個空間

? ? ? ? 因此時間復雜度為：O(N)

感謝各位大佬支持并指出問題，

????????????????如果本篇內容對你有幫助，可以一鍵三連支持以下，感謝支持！！！