《Programming Abstractions in C》学习第 73 天，p293-p302 总结，总计 10 页。
一、技术总结
1. 工夫复杂度
(1)quadratic time(二次工夫)
p293, Algorithms like selection sort that exhibit O(N^2) performance are said to run in quadratic time。
2. 线性查找(linear search)
p293, Because the for loop in the implementation executes n time, you expect the performance of LinearSearch——as its name implies——to be O(N)。工夫复杂度为 O(N)的查找称为线性查找。
3. 归并排序(merge sort)
书中并为对归并排序做严格的定义。p298, The merge operation, combined with recursive decomposition, gives rise to a new sorting algorithm called merge sort, which you can implement in straightforward way. The basic idea of the algorithm can be outlined as follows:
- Check to see if the array is empty or has only one element. If so, it must alread be sorted, and the function can return without doing any work. This condition defines the simple case for the recursion.
- Divide the array into two new subarrays, each of which is half the size of the original.
- Sort each of the subarrasy recursively.
- Merge the two subarrays back into the original one.
/*
* 伪代码
*/
static void Merge(int array[], int arr1[], int n1, int arr2[], int n2);
static int *CopySubArray(int array[], int start, int n);
void SortIntegerArray(int array[], int n);
/*
* Function: SortIntegerArray
* Usage: SortIntegerArray(array, n);
* ----------------------------------
* This function sorts the first n elements of array into
* increasing numerical order using the merge sort algorithm,
* which requires (1) dividing the array into two halves,
* (2) sorting each half, and (3) merging the halves together.
*/
void SortIntegerArray(int array[], int n) {
int n1, n2, *arr1, *arr2;
if (n <= 1) {return;}
n1 = n / 2;
n2 = n - n1;
arr1 = CopySubArray(array, 0, n1);
arr2 = CopySubArray(array, 0, n2);
SortIntegerArray(arr1, n1);
SortIntegerArray(arr1, n2);
Merge(array, arr1, n1, arr2, n2);
FreeBlock(arr1);
FreeBlock(arr2);
}
/*
* Function: Merge
* Usage: Merge(array, arr1, n1, arr2, n2);
* ----------------------------------------
* This function merges two sorted arrays (arr1 and arr2) into a
* single output array. Because the input arrays are sorted, the
* implementation can always select the first unused element in
* one of the input arrays to fill the next position in array.
*/
static void Merge(int array[], int arr1[], int n1, int arr2[], int n2) {
int p, p1, p2;
p = p1 = p2 = 0;
while (p1 < n1 && p2 < n2) {if (arr1[p1] < arr2[p2]) {array[p++] = arr1[p1++];
} else {array[p++] = arr2[p2++];
}
}
while (p1 < n1) {array[p++] = arr1[p1++];
}
while (p2 < n2) {array[p++] = arr2[p2++];
}
}
/*
* Function: CopySubArray
* Usage: CopySubArray(array, arr1, n1, arr2, n2);
* -----------------------------------------------
* This function makes a copy of a subset of an integer array
* and returns a pointer to a new dynamic array containing the
* new elements. The array begins at the indicated start
* position in the original array and continues for n elemnts.
*/
static int *CopySubArray(int array[], int start, int n) {
int i, *result;
result = NewArray(n, int);
for (i = 0; i < n; i++) {result[i] = array[start + i];
}
return result;
}
二、英语总结
1.quadratic 是什么意思？
答：In mathematics by 1660s;the algebraic quadratic euqation(二次方程, 1680s) are so called because they involve the square(x^2) and no higher power of x。这里要留神 quarter 是四分之一，然而 quadratic 是二次 (x^2) 的意思。
2.sophistication 是什么意思？
答：
(1)sophist > sophiticate > sophistication。
(2)sophist: one who makes use of fallacious arguments(诡辩者)。
(3)sophistication: u. the quality of being sophisticated(幼稚，复杂度)。
p293, The problem, howerver is that average-case analysis is much more difficult to carry out and typically requires considerable mathematical sophistication。这里比拟重要的一点是尽管这里用的是名词 sophistication，然而因为翻译的时候须要转一下，mathematical sophistication(简单的数学知识)。
3.average 用法总结
答：
(1)vt. to reach a particular amount as an average。主语能够是物也能够是人。翻译的时候须要灵便转变。
主语是物：Inquires to our office average 1000 calls a month.
主语是人：p294, From a practical point of view, it is often useful to consider how well an algorithm performs if you average its behavior over all possible sets of input data
三、其它
本书中作者解说归并排序 (merge sort) 和其它书还是有些不同的，从抉择排序算法开展，从而引出归并排序算法，能够和其它书进行比照浏览。
四、参考资料
1. 编程
(1)Eric S.Roberts，《Programming Abstractions in C》：https://book.douban.com/subject/2003414
2. 英语
(1)Etymology Dictionary：https://www.etymonline.com
(2) Cambridage Dictionary：https://dictionary.cambridge.org
欢送搜寻及关注：编程人(a_codists)