算法到底是什么？ _算法

算法的官方定义

算法（Algorithm）
一个有限指令集
接受一些输入（有些情况下不需要输入）
产生输出
一定在有限步骤之后终止
每一条指令必须
有充分明确的目标，不可以有歧义
计算机能处理的范围之内
描述应不依赖于任何一种计算机语言以及具体的实现手段

例1：选择排序算法的伪码描述/* 伪代码描述 */void SelectionSort (int List[], int N){ 将N个整数List[0]...List[N-1]进行非递减排序；从List[i]到List[N-1]中找最小元，并将其位置赋给MinPosition；将未排序部分的最小元换到有序部分的最后位置；}}/* C语言实现 */void SelectionSort (int List[], int N){ /* 将N个整数List[0]...List[N-1]进行非递减排序 */ for (i=0; i<N; i++){ MinPosition = ScanForMin(List, i, N-1); /* 从List[i]到List[N-1]中找最小元，并将其位置赋给MinPosition；*/ Swap(List[i], List[MinPosition]); /* 将未排序部分的最小元换到有序部分的最后位置； */}}# Python语言实现def selection_sort(lt, n): for i in range(n): min_position = scan_for_min(lt, i, n-1) swap(lt[i], lt[min_position])抽象 ——
【算法到底是什么？】List到底是数组还是链表（虽然看上去像数组）？
Swap用函数还是用宏去实现？
什么是好的算法通常通过下面两个指标衡量算法的好坏
空间复杂度S(n)
根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断。
时间复杂度T(n)
根据算法写成的程序在执行时耗费时间的长度。这个长度往往也与输入数据的规模有关。时间复杂度过高的低效算法可能导致我们在有生之年都等不到运行结果。
0101-例2-空间复杂度
/* c语言实现 */void PrintN (int N){if (N){ PrintN(N - 1); printf("%dn", N);} return;}# python语言实现def print_n(n: int): if n: print_n(n - 1) print(n)

文章插图

首先内存记录PrintN(100000)的状态，但由于是递归调用，会继续记录PrintN(99999)的状态，由于继续在递归调用，会继续记录PrintN(99998)的状态，……因此内存占用超限。
0101-例3-时间复杂度
方法1
f(x)=a
0
+a
1
x+?+a
n−1
x
n−1
+a
n
x
n
f(x)=a0+a1x+?+an−1xn−1+anxn
对于上述的多项式，我们可以使用以下代码实现：
/* c语言实现 */double f(int n, double a[], double x){int i; double p = a[0] for (i=1; i<=n; i++) p += (a[i] * pow(x, i)); /* pow会执行i次乘法 */ return p;}# python语言实现def f(n: int, a_list: list, x: float): p = a_list[0] for i in range(1, n): p += (a_list[i] * pow(x, i)) return p时间复杂度：
(1+2+?+n)=(n
2
+n)/2
T(n)=C
1
n
2
+C
2
n
(1+2+?+n)=(n2+n)/2T(n)=C1n2+C2n
方法2
但是上述的方法极其复杂，我们可以对多项式进行如下化简：
f(x)=a
0
+x(a
1
+(x(?(a
n−1
+x(a
n
))?))
f(x)=a0+x(a1+(x(?(an−1+x(an))?))
/* c语言实现 */double f(int n, double a[], double x){int i; double p = a[n]; for (i=n; i>0; i--) p = a[i-1] + x*p; /* 一次乘法 */ return p}# python语言实现def f(n: int, a_list: list, x: float): p = a_list[n] for i in range(0,n,-1): p = a_list[i-1] + x*p return p时间复杂度：
(1+1+?+1)n次
T(n)=Cn
(1+1+?+1)n次T(n)=Cn
综上：在分析一般算法的效率时，我们经常关注下面两种复杂度