算法

算法是一组用于解决具体问题的、明确的、有序的步骤或规则，能够在有限的时间内通过这些步骤得到问题的答案。

算法的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(n²) ：平方时间复杂度，常见于简单的嵌套循环算法，如冒泡排序。
• O(n³) ：立方时间复杂度，常见于三重嵌套循环的算法。
• 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\ast i\ast 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]\ast (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) 的额外空间），即除了输入数据本身占用的空间外，不需要额外申请大量存储空间。这样，算法直接在输入的数据结构上进行修改和操作，不借助辅助数组或数据结构。

原地算法的优点是节省内存资源，适合对空间要求较高的场景。例如，原地排序算法（如快速排序、堆排序）就是经典的原地工作的例子。