《算法导论》第二章笔记 (2)

首先,通过归并排序,对数组进行排序(因为后面用到的二分查找需要顺序表。并且题目只要求确认是否存在,并没有要求返回对应index,所以在一开始进行排序操作)。

外层通过循环,依次获得对应元素,根据branchTarget = target - array[i]这样的操作获得两个元素中的另一个元素。再通过二分查找,判断集合中是否存在对应的另一个元素。

归并排序的时间复杂度为nlgn,循环遍历的时间复杂度为n,二分查找的时间复杂度为lgn,所以最终的耗时为nlgn+n*lgn,故最终时间复杂度为nlgn。

具体实现,请看本章代码实现博客。

思考

由于该章的思考题,都需要进行公式计算与展示,而我并不会用MarkDown表示,所以就不写出来了。如果感兴趣,给各位一个资料(Algorithems Solutions)。

总结

其实这个章节还是比较简单的。算法上面举了一些有关排序的例子,以及一个折半查找的demo。数学方面,一方面需要还记得高中的数学归纳法,另一方面需要一定的排列组合的认识(进行复杂度的计算表)。

附录 参考

《算法导论》

Algorithems Solutions

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zywxjx.html