1.什么是算法
An algorithm is a clearly specified set of simple instructions to be followed to solve a problem.
2.算法分析
Algorithm analysis is the amount of computer memory and time needed to run a program (algorithm)
3.时间复杂度和空间复杂度
- 空间：运行所需要的内存
- 时间：运行所需要的时间
3.1 空间复杂度
3.1.1 组成
- 指令空间 instruction space
- 数据空间 data space（包括常量，变量，成员变量）
- 运行环境栈（to save information needed to resume execution of partially completed functions）‘
即分为两部分，即固定的部分和可变的部分（分别包括space for instructions,simple variables,fixed-size component variables,constants以及space for component variables,dynamical allocated space,recursion stack）
下面看几个例子
例子1
public static int SequentialSearch(int[] a, int x) {
int i;
for (i = 0; i < a.length && a[i] != x; i++) {
}
if (i == a.length)
return -1;
return i;
}
Total data space:
12 bytes : x,i,a[i],0,-1,a.length
each of them cost 2 bytes
Thus, S(n)=0
例子2
public static float Rsum(float[] a, int n) {
if (n > 0)
return Rsum(a, n - 1) + a[n - 1];
return 0;
}
Recursion stack space:
formal parameters : a (2 byte), n(2 byte) return address(2 byte)
Depth of recursion: n+1
Thus, S(n)=6(n+1)
3.2 时间复杂度
程序的执行时间为T(p)，T(p) = compile time + run time
identify one or more key operations and determine the number of times these are performed（找到一个或更多的关键操作并且指出它们执行需要的时间）
//Example 1
//finding the largest number in a[0:n-1]
public static int Max(int[] a, int n) {
//locate the largest element in a[0:n-1]
int pos = 0;
for (int i = 1; i < n; i++)
if (a[pos] < a[i]) pos = i;
return pos;
}
compare time : n-1
Example 2
//selection sort
0 1 2 3 4 5
21 25 49 25* 16 08
08 25 49 25* 16 21
08 16 49 25* 25 21
08 16 21 25* 25 49
08 16 21 25* 25 49
08 16 21 25* 25 49
public static void SelectionSort(int[] a, int n) {
//sort the n number in a[0:n-1].
for (int size = n; size > 1; size--) {
int j = Max(a, size);
swap(a[j], a[size - 1]);
}
}
对选择排序进行分析
- 每次调用Max(a,size)带来size-1次比较，所以总共的比较次数为：n-1+n-2+......+3+2+1=(n-1)*n/2
- 元素的移动一共进行了3(n-1)次（swap，交换两个元素的值，需要第三个变量）
Example3
//bubble sort
8 25 32 15 20 38 46 54 67
public static void Bubble(int[] a, int n) {
//Bubble largest element in a[0:n-1] to right
for (int i = 0; i < n - 1; i++)
if (a[i] > a[i + 1])
swap(a[i], a[i + 1]);
}
public static void BubbleSort(int[] a, int n) {
//Sort a[0:n-1] using a bubble sort
for (int i = n; i > 1; i--)
Bubble(a, i);
}
对冒泡排序进行分析
- 总共的比较次数为：(n-1)*n/2
Example 4
//Rank sort
r: 0 2 1 4 3
0 1 2 3 4
a: 8 25 16 30 28
public static void Rank(int[] a, int n, int[] r) {
//Rank the n elements a[0:n-1]
for (int i = 0; i < n; i++)
r[i] = 0;
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
if (a[j] <= a[i]) r[i]++;
else r[j]++;
}
public static void Rearrange(int[] a, int n, int[] r) {
//In-place rearrangement into sorted order
for (int i = 0; i < n; i++)
while (r[i] != i) {
int t = r[i];
swap(a[i], a[t]);
swap(r[i], r[t]);
}
}
对Rank排序进行分析
- 比较次数：(n-1)*n/2
- 移动次数：2n
最好的，最坏的以及平均的操作数，平均的操作数通常难以得出。因此，我们的分析从最好以及最坏操作数来进行
