0%

《算法图解》Grokking algorithms（上）

Posted on Edited on In

《算法图解》Grokking algorithms（上）

最近被斌叔推荐的一本算法入门书籍，简洁精巧地讲了十几个常用算法，“像小说一样有趣”。它使我能更轻松地理解编程中的常用算法思想，我在这里分享其中的知识点和代码，原书中使用的是python2.7，我使用的是python3.6。文中插图均为原书中的配图，生动形象，同时这本书的github链接：https://github.com/egonschiele/grokking_algorithms

这本书的第一章介绍了第一种算法——二分查找和大O表示法。大O表示法指出了算法的运行时间，算法运行时间并不以秒为单位而是从其增速的角度来衡量。在第四章中介绍了平均情况和最糟情况。

选择排序 Selection sort

数组和链表是两种基本的数据结构，本书的第二章通过选择排序来更好的理解数组。
数组在储存是必须是连续的，而链表因为使用地址指向而可以分开储存。所以，数组的读取速度很快，但插入和删除速度很慢，即如下图所示。
img

那么，本书的第二种算法——选择排序通过将数据从大到小或从小到大排列，运行时间即为O(n^2)。
下面是将数组元素从小到大排列的代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Finds the smallest value in an array
def findSmallest(arr):
  # Stores the smallest value
  smallest = arr[0]
  # Stores the index of the smallest value
  smallest_index = 0
  for i in range(1, len(arr)):
    if arr[i] < smallest:
      smallest_index = i
      smallest = arr[i]      
  return smallest_index

# Sort array
def selectionSort(arr):
  newArr = []
  for i in range(len(arr)):
      # Finds the smallest element in the array and adds it to the new array
      smallest = findSmallest(arr)
      newArr.append(arr.pop(smallest))
  return newArr

Input

1
print(selectionSort([5, 3, 6, 2, 10]))

Output

1
[2, 3, 5, 6, 10]

递归recusion

“如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。”

递归是一种自己调用自己的函数，它易于理解，但不一定在计算性能上有优势。编写递归函数时，必须告诉它何时停止递归。因此，递归函数的组成：基线条件（base case）和递归条件（recursive case）。倒计时函数的代码示例：

1
2
3
4
5
6
def countdown(i):
	print(i)
	if i<= 1:         #base case
		return
	else:             #recursive case
		countdown(i-1)
栈

栈是一种数据结构，计算机在内部使用被称为调用栈（call stack）的栈。当你调用函数时，计算机用栈来表示为这个函数调用分配的一块内存。那么，当调用某个函数时还需调用其他函数的情况，如何理解栈？

  • 调用其他函数时，当前函数暂停并处于未完成状态。
  • 调用其他函数时，计算机为其分配一块内存位于该函数上，在函数调用返回后，栈顶的内存块被弹出。

使用栈虽然方便，但是储存详尽的信息可能占用大量的内存，如果调用递归函数但不小心导致它没完没了运行，则最后会因为栈溢出而终止。

快速排序Quicksort

示例为使用循环和递归完成累加：

1
2
3
4
5
6
7
8
9
10
11
12
#loop sum
def sum(arr):
  total = 0
  for x in arr:
    total += x
  return total

#recursive sum
def sum(list):
  if list == []:
    return 0
  return list[0] + sum(list[1:])

递归式解决问题的思路是一种著名的问题解决方法——分而治之（divide and conquer，D&C）。
快速排序就是一个重要的D&C算法。它通过设置基准值（pivot）后对数组进行分区（partitioning），再在分区进行相同的操作来完成。
快速排序的代码：

1
2
3
4
5
6
7
8
9
10
11
12
def quicksort(array):
    if len(array) < 2:
    # base case, arrays with 0 or 1 element are already "sorted"
        return array
    else:
        # recursive case
        pivot = array[0]
        # sub-array of all the elements less than the pivot
        less = [i for i in array[1:] if i <= pivot]
        # sub-array of all the elements greater than the pivot
        greater = [i for i in array[1:] if i > pivot]
        return quicksort(less) + [pivot] + quicksort(greater)

快速排序算法的平均运行时间为O(n log n)，而最糟情况则为O(n^2)。下图为最佳情况，也就是平均情况。
quick

散列表Hash tables

散列表是一种包含额外逻辑的强大的数据结构，它使用散列函数来确定元素的储存位置。Python使用的散列表实现为字典。
散列表可以用于查找、防止重复、储存缓存以缓解服务器的压力。
那么，散列表是如何储存的？
它虽然模拟映射关系，但是不可能总是将不同的键映射到数组的不同位置。当遇到冲突（collision）情况，即两个键映射到了同一个位置，就在这个位置存储一个链表。所以，一个好的散列函数将极少导致冲突，使散列表的速度不会太慢。要避免冲突，需要有：

  • 较低的填装因子；
  • 良好的散列函数。

广度优先搜索Breadth-first search，BFS

广度优先搜索是一种用于图的查找算法，能找出两样东西之间的最短距离。

  • 图由节点和边组成，用于模拟不同的东西是如何相连的。
  • 广度优先搜索采用“队列（queue）”的数据结构。和栈后进先出(Last In First Out) 的数据结构相对，是一种先进先出(First In First Out) 的数据结构。

广度优先搜索的运行时间为O（人数+边数），写作O(V+E)，其中V为顶点（vertice）数，E为边数。

  • 拓扑排序可以穿建一个有序的任务列表；
  • 树是图的子集，树是一种完全单向指向的图。

以上是该书的前半部分内容，后半部分待整理。