算法导论第二章小试牛刀

Author: bakari   Date: 2015.9.11

《算法导论》真是一本让人又爱又恨的书,爱自然是因为它精简凝练的算法呈现,读来让人欲罢不能;至于恨,是因为它在进行算法分析的时候所体现的数学思想太过于强大, 对于我这种数学不上不下的人来说,自然有几分畏难,以致于我很早就接触这本书,前前后后也粗略地看过几遍,但感觉每一遍都像是重新看一样,没有掌握其本质,本来一直都有着一个目标就是看一章,记一章读书笔记,但是本身固有的完美主义又强迫我说没看懂就不要轻易下笔,所以时至今日,我仍然没有付诸行动。现在由于面临找工作技术菜的窘境,拿到这本书的最新版第三版的时候,感觉又像是重新读一样,一些常见常用的算法,我仍然不能快速而准确的写出代码。这样的实践能力让我的危机感一下子到了极点,我甚至都怀疑自己是不是读书越高,能力反而退化得越快。所以,遵照那句老话:只要你想开始,任何时候都不算太晚。所以,又再一次拾起这本书,我也不给自己太多期望说读一章写一章读书笔记,我只希望能为我明年找工作留下一点努力的痕迹,不让自己觉得有努力的机会而没有努力而觉得遗憾。

第一章balabala,写一堆算法的定义和特点,这里不在过多记录,我也提炼不出什么有技术含量的东西,不过末尾有一句话值得记录一下:是否具有算法知识与技术的坚实基础是区分真正熟练的程序员与初学者的一个特征。这句话其实对于行内人来说,是一句废话,谁不知道呢。之所以记录它,是因为在这一章中,也就这一句话以其精炼的句子结构浓缩了精华,更把一个读者不甘做小白的心理刻画得淋漓尽致,巴不得今天通宵也要把这本书啃完。

关于算法,我认为掌握它最主要的是需要掌握两个方面:设计和分析,这也是算法的核心之处。这本书好就好在它是从算法的核心来展开算法章节的写作。所以,本书刚开始的几章都是着眼于分析算法的本质:算法的执行效率,也就是算法的时间复杂度。第二章的主要内容点就在于通过一些简单的例子入手,步步递进分析算法的复杂度,同时这些例子又是比较有代表性:比如重点讲到的基本排序算法,插入排序和合并排序,还有在习题部分讲到的线性查找和二分查找。通过第二章对分析算法复杂度有初步印象之后,第三章趁热打铁引出相关描述算法复杂度的符号,如此便对如何表示一个算法的复杂度,以及如何分析算法的复杂度有了比较深入完整的认识。而这些也正是很多公司喜欢刁难你的地方。

对于一个读者,我所能做的也就是记录下自己编程实践的结果,希望能通过动动手指头加深一下印象,也不至于留下一种“我来过这个世界,而这个世界没有留下我的痕迹”的失落感。我一直在想怎么来组织笔记的结构,也看了一些网友的博客,大致可以有三种方案:是看了书之后提炼自己的想法,还是照着书把重点的东西摘抄一边,亦或是把课后书本里的编程题还有课后习题自己动手实践一遍后在搬上来,第二种方法很明显自己是学不到东西的,pass,其余两个一起拥有是最好的,前面也说过,我有一点完美主义的倾向,所以,我自然选择两者都能兼具,不管花多少时间,我都愿意。所以,如你见到的,洋洋洒洒写了上面这一堆文字,但我也不能保证自己能完整的呈现,因为这还有很多外界因素的干扰,时间是最大的一个,我只能说,我一定会尽力的,不管是一天一篇,还是一个星期一篇,或更久,总之,我会写一个专题。

下面记录几个基础算法的实现,很早之前我也写过相关的文章,在此就不多说,直接贴代码吧。

1、插入排序:关于插入排序,我之前写过一篇文章,引申了三种插入排序的形式,详见:https://cloud.tencent.com/developer/article/1017826

除此之外,还有一种插入排序的形式,即递归式(其实基本的排序算法,选择,冒泡等都有递归的排序版本),分析递归的排序算法,主要是融会贯通其算法复杂度的分析方法(貌似递归算法最容易分析算法复杂度的,因为有递归式),如下:

2、插入排序:非递归版本:

 1 //insertion sort: non-recursive
 2 //from big to small, only just arr[i] > key
 3 void InsertionSort(int arr[], int len)
 4 {
 5     if (arr == NULL || len == 0)
 6         return;
 7 
 8     for (int j = 1; j < len; j ++) {
 9         int key = arr[j];
10         int i = j - 1;
11         while(i >= 0 && arr[i] < key) {
12             arr[i+1] = arr[i];
13             i --;
14         }
15         arr[i+1] = key;
16     }
17 }

3、插入排序:递归版本:(有很多实现版本,我们采用从后向前插的方式)

——>参见习题2.3-4:为排序A[1-n],先递归排序A[1-n-1],然后再将A[n]插入到已排序的A[1-n-1]里,为此,可以写出递归式为:

T(n) = T(n-1) + n

 1 //insertion sort: recursive
 2 void InsertionSort_Recursive(int arr[], int len)
 3 {
 4     if (len > 1) {
 5         InsertionSort_Recursive(arr, len-1);
 6         Insertion(arr, len);
 7     }
 8 }
 9 
10 void Insertion(int arr[], int len)
11 {
12     if (len > 1) {
13         int key = arr[len - 1];
14         int i = len - 2;
15         while(i >= 0 && arr[i] > key) {
16             arr[i+1] = arr[i];
17             i--;
18         }
19         arr[i+1] = key;
20     }
21 }

4、选择排序:习题2.2-2

 1 //selection sort
 2 void SelectionSort(int arr[], int len)
 3 {
 4     if (arr == NULL || len == 0)
 5         return;
 6     
 7     for (int i = 0; i < len - 1; i ++) { //!!! n - 1
 8         int key = arr[i];
 9         int index = i;
10         for (int j = i + 1; j < len; j ++) {
11             if (arr[j] < key) {
12                 key = arr[j];
13                 index = j;
14             }
15         }
16         arr[index] = arr[i];
17         arr[i] = key;
18     }
19 }

5、n位二进制整数相加问题:A[1-n] + B[1-n] = C[1-n+1]——>习题2.1-4

 1 //binary array addition - 2.1-4
 2 void BinaryArrayAdd(char arrA[], char arrB[], char arrC[], int len) 
 3 {
 4     if (len == 0)
 5         return;
 6     
 7     ReverseArray(arrA, len);
 8     ReverseArray(arrB, len);
 9     int lenC = len + 1;
10     
11     int flag = 0;
12     for (int i = 0; i < len; i ++) {
13         int value = arrA[i] + arrB[i] + flag;
14         arrC[i] = (arrA[i] + arrB[i]) % 2;
15         if (value < 2) //相加>2,表示有进位
16             flag = 0;
17         else
18             flag = 1;
19     }
20     arrC[lenC] = flag;
21 
22     ReverseArray(arrC, lenC);
23 }

6、归并排序,末尾有“哨兵”的版本:

 1 //merge sort 
 2 //note: right is the index of end
 3 void MergeSort(int arr[], int left, int right)
 4 {
 5     if (left < right){
 6         int mid = (left + right)/2;
 7         MergeSort(arr, left, mid);
 8         MergeSort(arr, mid + 1, right);
 9         MergeDontFlag(arr, left, mid, right);
10     }
11 }
12 
13 //has the 'end flag'
14 void MergeWithFlag(int arr[], int left, int mid, int right)
15 {
16     int nLen1 = mid - left + 1;
17     int nLen2 = right - mid;
18     
19     int *arrA = new int[nLen1+1];
20     int *arrB = new int[nLen2+1];
21 
22     for (int i = 0; i < nLen1; i ++)
23         arrA[i] = arr[left + i];
24     for (int j = 0; j < nLen2; j ++)
25         arrB[j] = arr[mid + 1 + j];
26     
27     //the 'end flag'
28     arrA[nLen1] = INT_MAX;
29     arrB[nLen2] = INT_MAX;
30     
31 
32     int i = 0, j = 0;
33     for(int k = left; k <= right; k ++) {
34         if (arrA[i] <= arrB[j]) {
35             arr[k] = arrA[i];
36             i++;
37         }
38         else {
39             arr[k] = arrB[j];
40             j ++;
41         }
42     }
43     delete arrA;
44     delete arrB;
45     arrA = NULL;
46     arrB = NULL;
47 }

7、归并排序,末尾没“哨兵”版本:——>习题2.3-2

 1 void MergeDontFlag(int arr[], int left, int mid, int right)
 2 {
 3     int nLen1 = mid - left + 1;
 4     int nLen2 = right - mid;
 5 
 6     int *arrA = new int[nLen1+1];
 7     int *arrB = new int[nLen2+1];
 8 
 9     for (int i = 0; i < nLen1; i ++)
10         arrA[i] = arr[left + i];
11     for (int j = 0; j < nLen2; j ++)
12         arrB[j] = arr[mid + 1 + j];
13 
14     int i = 0, j = 0, k = 0;
15     for(k= left; i < nLen1 && j < nLen2; k ++) {
16         if (arrA[i] <= arrB[j]) {
17             arr[k] = arrA[i];
18             i++;
19         }
20         else {
21             arr[k] = arrB[j];
22             j ++;
23         }
24     }
25     while (i < nLen1) {
26         arr[k++] = arrA[i++];
27     }
28     while (j < nLen2) {
29         arr[k++] = arrB[j++];
30     }
31     delete arrA;
32     delete arrB;
33     arrA = NULL;
34     arrB = NULL;
35 }

8、折半查找——>习题2.3-5

关于这个算法还有很多经典的问题,以及很多容易出错的点,等找个时间做一个专题总结,这个算法太典型了,而且也是笔试面试中非常常见的。

 1 bool BinaryFind(int arr[], int len, int key)
 2 {
 3     if (len == 0)
 4         return false;
 5     int nLeft = 0;
 6     int nRight = len - 1;
 7 
 8     while (nLeft <= nRight) {
 9         int nMid = nLeft + (nRight - nLeft) / 2; //!!!避免溢出
10         if (key < arr[nMid])
11             nRight = nMid - 1;
12         else if (key > arr[nMid])
13             nLeft = nMid + 1;
14         else
15             return true;
16     }
17     return false;
18 }

9、习题2.3-7:描述一个运行时间为O(nlgn)的算法,给定n个整数的集合S和一个整数x,该算法能确定S中是否存在两个其和刚好为x的元素。

这个题放在排序一节中,自然会用到排序算法,思考之后,我们可以得到这样一个算法思路:

  首先对S[1...n]进行非降序排序,然后设置两个指向标i=1,j=n,执行下面的操作:

          S[i] + S[j]  = X,  返回true

                < X,  i = i+1

                > X,  j = j-1

          如果 i>j 返回false

  时间复杂度分析:排序为Θ(nlgn),之后为Θ(n),算法的时间复杂度为Θ(nlgn)

 1 //FindAddition
 2 //find (a+b=x) from a array, if can, return true
 3 bool FindAddition(int arr[], int len, int xKey)
 4 {
 5     if (len == 0 || len == 1)
 6         return false;
 7     int iL = 0;
 8     int iR = len - 1;
 9     while (iL < iR) {
10         if (arr[iL] + arr[iR] < xKey)
11             iL ++;
12         else if (arr[iL] + arr[iR] > xKey)
13             iR --;
14         else
15             return true;
16     }
17     return false;
18 }

10、求逆序对,习题2-4

要求:给出一个确定在n个元素的任何排列中逆序对数量的算法,最坏情况需要O(nlgn)的时间复杂度。(逆序对形如下面的序列:i<j, A[i] > A[j])

题目已经提示修改归并排序可以完成,插入法是求逆序对的暴力求法,因为插入排序的次数就是对应的逆序对的数目。采用归并排序的分治策略,可以这样来求逆序对:

分治就是将一个原始的数组平均分成两部分,如果左边部分A[i] < A[j],则不存在逆序对;如果A[i] > A[j],因为A中从A[i]往后的数都与A[j]构成逆序对,即A[i] - A[n1.length - i],所以逆序对的数量加n1.length - i。有了这样的思路,只用修改归并排序很少的代码就能实现求逆序对。如下:

 1 int MergeInversion(int arr[], int nLeft, int nRight);
 2 int Merge(int arr[], int p, int q, int r);
 3 
 4 //用归并排序找逆序对
 5 int MergeInversion(int arr[], int nLeft, int nRight)
 6 {
 7     int nInversion = 0;
 8     if (nLeft < nRight) {
 9         int nMid = (nLeft+nRight) >> 1;
10         nInversion += MergeInversion(arr, nLeft, nMid);
11         nInversion += MergeInversion(arr, nMid+1, nRight);
12         nInversion += Merge(arr, nLeft, nMid, nRight);
13     }
14     return nInversion;
15 }
16 
17 int Merge(int arr[], int p, int q, int r)
18 {
19     int n1 = q - p + 1;
20     int n2 = r - q;
21     int *left = new int[n1];
22     int *right = new int[n2];
23 
24     int i,j;
25     for (i = 0; i < n1; i ++)
26         left[i] = arr[p+i];
27     for (j = 0; j < n2; j ++)
28         right[j] = arr[q+1+j];
29 
30     i = 0;
31     j = 0;
32     int k = p;
33     int nInverCount = 0; //逆序对的数目
34 
35     while (i < n1 && j < n2) {
36         if (left[i] <= right[j]) 
37             arr[k++] = left[i++];
38         else {//假如左边子序列的数大于右子序列,则逆序对数为n1 - i;
39             arr[k++] = right[j++];
40             nInverCount += (n1 - i);
41         }
42     }
43     while (i < n1)
44         arr[k++] = left[i++];
45     while (j < n2)
46         arr[k++] = right[j++];
47     
48     delete left;
49     left = NULL;
50     delete right;
51     right = NULL;
52     
53     return nInverCount;
54 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏云时之间

算法导论系列:分治算法

说起分治法,大家一定也都听过秦始皇采用郡县制将国家分为三十六郡的故事,我们常说”山高皇帝远”,意思就是山高路远,皇帝都管不了,实际上无论皇帝多远,山有多高,整个...

1272
来自专栏数据结构与算法

一种递推组合数前缀和的Trick

\(S(n, m)\)可以看做是杨辉三角上的一行,而\(S(n+1, m)\)是他的下一行

2103
来自专栏我杨某人的青春满是悔恨

函数式思维

自从大四看了三章《SICP》之后我就自诩为一个函数式编程爱好者,之前也在公司分享过一个 Haskell 的 Topic,效果非常糟糕,讲到后来已经没剩几个人了,...

1001
来自专栏Code_iOS

数据结构?

数据结构可以实现一种或多种抽象数据类型,而抽象数据类型(Abstract Data Type [ADT])就是一种数学的抽象,一些操作的集合【插入、删除等操作】...

1332
来自专栏编程

知道这几点你就学会了Python!

由于Python目前在各个领域都比较火,尤其是人工智能和量化金融方面的应用,更让人趋之若鹜,还不会Python的你是不是落伍了呢。下面就是我的不装逼教你学Pyt...

2255
来自专栏C语言及其他语言

初学C语言的学习计划

背景:很多同学在学习C语言的过程中,常常会遇到这样的问题,即“教材看完了,知识点也懂,但写不出来程序”,这段时间,我们通过长期与有多年C语言研究经验的教授、教师...

3624
来自专栏窗户

scheme实现最基本的自然数下的运算

  教一个基本没编过什么程序的朋友scheme,为什么教scheme呢?因为他想学,因为一直听我鼓吹,而他觉得他自己多少有C语言一点基础,而又因为我觉得函数式才...

773
来自专栏LinkedBear的个人空间

【挑战剑指offer】系列02:替换空格 原

本系列的算法原题来自于“牛客网-剑指offer”,写这个板块,不仅仅是解决算法问题本身,更是手动提高难度、自行变式,思考更多的解决方案,以带给自己一些启发。

1223
来自专栏计算机视觉与深度学习基础

主席树POJ2104

求区间第k大数是多少 用我惯用的线段树写法似乎不适合写主席树,看别人的代码好半天才看懂 用root表示每一个前缀树的根,思想大致是由第i-1个树构成的树建第i个...

2599
来自专栏企鹅号快讯

编程世界的沟沟坎坎

我相信每一个想学习编程或者经历过编程实践的人,在刚开始的时候都会遇到一些沟沟坎坎,尤其是对编程里面的一些概念,比如说Java语言是面向对象的、C语言是面向过程的...

2249

扫码关注云+社区

领取腾讯云代金券