算法

算法是一組用于解決具體問題的、明確的、有序的步驟或規則，能夠在有限的時間內通過這些步驟得到問題的答案。

算法的5個重要特性：

1. 有窮性：算法必須在有限的步驟內結束，不能無限循環，保證最終能夠得到結果。
2. 確定性：算法的每一步操作都有明確的定義，沒有歧義，保證執行結果唯一。
3. 可行性：算法的每個步驟都必須是可行的，即能夠在有限時間內通過基本操作完成。
4. 輸入：算法具有零個或多個輸入，輸入是算法運行所需要的數據。
5. 輸出：算法至少有一個或多個輸出，輸出是算法處理后的結果。

也就是說，一個基本的算法，必須能夠在有限的步驟內將輸入的數據通過具有確定含義的指令轉換為所需要的輸出結果。

以溫度傳感器原始數據的轉化算法為例

1. 有窮性：算法在有限步驟內完成原始數據的讀取、處理和轉化，確保不會無限循環，最終輸出轉換后的溫度值。
2. 確定性：相同的傳感器原始數據通過算法處理后，每次都得到相同且明確的溫度值，步驟明確無歧義。
3. 可行性：算法使用的操作（如數據讀取、數學計算等）都是實際可執行的，能夠在傳感器所在的硬件環境中完成。
4. 輸入：算法的輸入是傳感器采集到的原始數據（例如電壓值或數字信號），這些數據用于后續轉換計算。
5. 輸出：算法輸出轉換后的溫度值（如攝氏度或華氏度），供系統顯示或進一步處理使用。

設計一個好的算法還應該考慮什么？

算法的正確性：即能正確的解決問題。可讀性：算法閱讀起來清晰明了，便于理解。健壯性：算法對于非法數據能做出相應的處理，不會輸出奇怪的數據。高效率與低存儲需求：即算法既要執行的快而準，又要不占用過多存儲空間。

還是拿溫度傳感器來講：好的算法要能正常將溫度值轉化出來；寫的代碼要讓人能看懂好理解；當測試環境溫度超出溫度傳感器量程的時候要做相應處理，不能說單純輸出最大值或者最小值；溫度轉換過程花費的時間要少，占用的flash和ram都要少。（既要又要還要）

衡量一個算法的效率

通常衡量算法效率是通過時間復雜度和空間復雜度來描述的。但是一個算法的優劣，不能僅僅依靠時間復雜度和空間復雜度來做出評判。在實際應用中，算法首先要能正確解決問題，然后在效率和內存占用這兩者之間進行權衡。

時間復雜度

一個算法中所有語句在該算法中被重復執行的次數被定義為T(n)，時間復雜度則是主要分析T(n)的數量級。因此，通常將算法中基本運算的執行次數的數量級作為該算法的時間復雜度。（即取T(n)中隨n增長最快的項，將其系數置為1，作為時間復雜度的度量）。

1. 最壞時間復雜度（Worst-case Time Complexity）：指算法在所有可能的輸入中，運行時間最長的情況所對應的時間復雜度。它保證了算法在任何輸入下的最大耗時。
2. 平均時間復雜度（Average-case Time Complexity）：指算法在所有可能輸入的概率分布下，運行時間的期望值。它反映了算法在一般情況下的性能表現，但計算比最壞情況復雜。
3. 最好時間復雜度（Best-case Time Complexity）：指算法在所有可能輸入中，運行時間最短的情況所對應的時間復雜度。通常用于了解算法在理想條件下的表現，但不能代表算法的普遍效率。

常見的漸近時間復雜度（從小到大排列）為：

• O(1) ：常數時間復雜度，執行時間固定，不隨輸入規模變化。
• O(log n) ：對數時間復雜度，例如二分查找。
• O(n) ：線性時間復雜度，執行時間隨著輸入規模線性增長。
• O(n log n) ：線性對數時間復雜度，常見于高效排序算法如歸并排序、快速排序。
• O(n2) ：平方時間復雜度，常見于簡單的嵌套循環算法，如冒泡排序。
• O(n3) ：立方時間復雜度，常見于三重嵌套循環的算法。
• O(2^n) ：指數時間復雜度，常見于遞歸求解所有子集等問題。
• O(n!) ：階乘時間復雜度，常見于全排列問題。

時間復雜度的計算

單層循環的時間復雜度計算

觀察變量隨次數的變化規律。

確定循環退出條件。

直接求循環的實際循環次數t。

舉個例子

x = 2
while(x < n/2)x = 2 * x; 

假設運行t次程序退出循環，可得x的值隨t的變化如下：

t	1	2	3	4	…
x	4	8	16	32	…

可以得到：
$$\begin{gathered} x=2^{t+1} \\ 當：x=n/2時退出循環 \\ 聯立求解t的值得到：t=lo{g}_{2}n+2 \\ 找到增長最快的項為lo{g}_{2}n,系數為1 \\ 所以時間復雜度O(n)=lo{g}_{2}n \end{gathered}$$

再舉個例子

void func(int n)
{int i = 0;while(i*i*i <= n)i++;
}

假設運行t次程序退出循環，可得x的值隨t的變化如下：

t	1	2	3	4	…
i	1	2	3	4	…

可以得到：
$$\begin{gathered} i=t \\ 當：i?i?i=n時退出循環 \\ 聯立求解t的值得到：t=\sqrt[3]{n} \\ 找到增長最快的項為\sqrt[3]{n},系數為1 \\ 所以時間復雜度O(n)=\sqrt[3]{n} \end{gathered}$$

兩層循環的時間復雜度計算

1. 首先確定外層循環的實際循環次數t作為內層循環次數求和的項數；

2. 然后列出每個外層循環下內層的循環次數；

3. 最后求和。

舉個例子

int m = 0,i,j;
for(i = 1; i <= n; i++)for(j = 1; j <= 2*i; j++)m++;
計算m++語句的執行次數

先把內層看成O(1)，那么外層循環次數為n，再看內層循環的 j 隨運行次數變化：

t_n(項數)	1	2	3	4	…
j	2	4	6	8	…

即：
$$\begin{gathered} 得到j與t_n的關系為:j=2t_n \\ 得到總次數為等差數列求和:總次數=(2+2t_n)t_n/2 \\ 已知:內循環退出的臨界點為j=2i,所以t_n=i,所以總次數=(2+2i)i/2 \\ 又已知:外循環退出的臨界點為i=n;所以總次數=n(n+1) \\ 得到執行次數為:n(n+1) \end{gathered}$$

再舉個例子

int sum = 0;
for(int i=1; i<n; i*=2)for(int j=0; j<i; j++)sum++;
求時間復雜度

先把內層看成O(1)，那么外層循環次數為 log?n，再看內層循環的 j 隨運行次數變化：

t_n(項數)	1	2	3	4	…
j	1	2	4	8	…

即
$$\begin{gathered} 得到j與t_n的關系為:j=2^{t_n} \\ 得到總次數為等比數列求和，公比為2，首項為1，項數為t_n?1:總次數=2^{t_n?1}?1 \\ 已知:內循環退出的臨界點為j=i,所以2^{t_n}=i,即t_n=lo{g}_{2}i,所以總次數=2^{lo{g}_{2}i?1}?1 \\ 又已知:外循環退出的臨界點為i=n;所以總次數=2^{lo{g}_{2}n?1}?1 \\ 化簡得總次數為:n/2?1;時間復雜度為O(n) \end{gathered}$$

小結

為了計算內層循環次數累加求和的項數，可以先把內層的時間復雜度看作O(1)，然后計算這個條件下外層循環總次數，這樣計算出來的外層循環總次數就是內層循環次數累加求和的項數了

再舉個例子

for(i = n-1; i > 1; i--)for(j = 1; j < i; j++)if(A[j] > A[j+1])A[j] 和 A[j+1]對換

這個就相當于求最壞時間復雜度。

首先把內層看作O(1)，那么外層循環次數為 (n-2)，再看內層循環的 j 隨運行次數變化：

t_n(項數)	1	2	3	4	…
j	n-2	n-3	n-4	n-5	1

所以可知：總次數是一個等差數列求和，首項為 (n-2) ，尾項為 1，項數為 (n-2)。

得到：
$$\begin{gathered} 總次數=([(n?2)+1]?(n?2))/2=(n?1)(n?2)/2 \\ 時間復雜度為:O(n^2) \end{gathered}$$

多層循環的時間復雜度計算

從內到外進行計算，即內層的次數求和，求和項的項數為相對內層而言的外一層循環看作單層循環時的循環次數。從最內層開始計算，一層一層向外求和。

舉例說明

for(i = 1; i <= n; i++) {             // 外層：n次for(j = 1; j <= i; j++) {         // 中層：i次for(k = 1; k <= j; k++) {     // 內層：j次// O(1)}}
}

• 內層循環復雜度：
  $$O(j)$$

• 中層循環總次數：
  $$\sum _{j=1}^{i}j=\frac{i(i+1)}{2}=O(i^2)$$

• 外層循環總次數：
  $$\sum _{i=1}^{n}O(i^2)=O\left(\sum _{i=1}^n{i}^2\right)=O\left(\frac{n(n+1)(2n+1)}{6}\right)=O(n^3)$$

空間復雜度

空間復雜度S(n)定義為該算法所需的存儲空間，它是問題規模n的函數。

算法的原地工作（In-place）：是指算法在執行過程中，只使用常數級別的額外空間（通常是 O(1) 的額外空間），即除了輸入數據本身占用的空間外，不需要額外申請大量存儲空間。這樣，算法直接在輸入的數據結構上進行修改和操作，不借助輔助數組或數據結構。

原地算法的優點是節省內存資源，適合對空間要求較高的場景。例如，原地排序算法（如快速排序、堆排序）就是經典的原地工作的例子。