/* 伪代码描述 */
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
综上：在分析一般算法的效率时，我们经常关注下面两种复杂度
由于平均复杂度的计算难度远远大于最坏情况复杂度，因此通常考虑最快情况复杂度，即T
worst
(n)≥T
avg
(n)
Tworst(n)≥Tavg(n)
对于算法的复杂度，没有必要求出一个精确值，只需要粗略的知道算法的增长趋势即可。
分析算法效率时，我们总是希望找到O
O时最大的上界；找到Ω
Ω时最小的下界。
下面三张图表示算法复杂度为不同函数时对应的耗时：
综上：一个专业的程序，设计了一个O(N
2
)
O(N2)的算法，应该本能的想到是否能把他改进为O(Nlog
N
)
O(NlogN)的算法。
京公网安备 11010802035086号