ScalersTalk成长会算法小组第5周学习笔记

Scalers点评：：成长会的算法小组已经启动，这是第5周的学习笔记。

写在前面的话：Algorithms + Data Structures = Programs。程序的运行效率很大程度上取决于程序所采用的算法的性能。如果你想提高自己的编程能力，对程序的运行效率有追求，那么快加入和我们一起学习算法吧。算法小组是成长会内部小组，如果你想和我们一起学习算法，你需要是成长会成员，并且完成相关进群任务，欢迎做完入群任务后发给[S157]激流。

往期日志：

本周学习情况

本周（20160222-20160228）学习[MITOPENCOURSE](
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/index.htm)上的6.006的第7个和第8个 lecture，并开始第四次线上做题。

笔记汇总

Lower_Bound：

1.Searching

对一个有n个数的数组进行查找，时间复杂度的下限是O(log(n))。

2.Sort

对一个有n个数的数组进行排序，时间复杂度的下限是O(nlog(n))。

Counting_Sort：

1.算法思想

计数排序不是基于比较的排序方法，而是通过用空间换时间的方法来进行排序，其实这也就是哈希的思想。

算法的核心思想就是开辟一个新的数组，然后对原来数组进行遍历，把元素映射到新数组的对应位置中，如果映射的位置相同可以做成链表。最后再重新开一个新数组，然后把第二个数组中的元素依次放到新数组中，这样排序就做好了。

counting_sort L = array of k empty lists for j in range(n): L[key(A[j])].append(A[j]) ouput =  for i in range(k): output.extend(L[i])

2.Time Complexity

从上面的代码看出，T(n) = O(k+n)，k是待排序数组中的不相同元素的个数。

Radix_Sort：

基数排序就是对于数组中的每个元素，先对其最低有效位进行排序，然后再对第二个有效位进行排序，直到最高有效位也排序好，这样整个数组也排序好了，下面是Radix_Sort的一个例子：

Hash：

Hash是一种用空间换时间的策略，Hash在很多编程语言中都有相关的类库的实现，在很多场景中也有应用。Hash就是把一个空间中的Key映射到一个table中，这个映射需要通过哈希函数来完成。下面是哈希的一个例子：

一般来说哈希表的大小都会比原始空间中Key的个数来的小，这样就会有冲突。

1.Chaining

一种解决方法就是把相同哈希值的元素直接用链表连在一起。下面是Chaining的一个例子：

• 通过Chaining来解决冲突，查找一个元素需要遍历T[h(key)]。

• Worst case:所有的Key都被哈希到同一个slot，每次操作都需要O(n)。

线上做题leetcode

[147. Insertion Sort List](https://leetcode.com/problems/insertion-sort-list/)

[143. Reorder List](https://leetcode.com/problems/reorder-list//)

第一道题：在链表中进行插入排序。总体思路和在数组中进行插入排序类似。第二道题：先找出链表的中点，然后把链表分成两部分。把第二个链表逆序，再把两个链表合并。

ScalersTalkID:scalerstalk

本微信公众号作者Scalers，游走在口译世界的IT从业者。微信公众号ScalersTalk，网站ScalersTalk.com，口译100小时训练计划群C 456036104

成长会是由Scalers发起的面向成长、实践行动，且凝聚了来自全球各地各行各业从业者的社群。有意入会者请和Scalers直接联系，我和其他会员会和你直接交流关于成长行动等各方面的经验教训。2016年成长会持续招募中，参见做能说会写的持续行动者：ScalersTalk成长会2016年会员计划介绍(2016.2更新)