《算法图解》Grokking-algorithms(上)
最近被斌叔推荐的一本算法入门书籍,简洁精巧地讲了十几个常用算法,“像小说一样有趣”。它使我能更轻松地理解编程中的常用算法思想,我在这里分享其中的知识点和代码,原书中使用的是python2.7,我使用的是python3.6。文中插图均为原书中的配图,生动形象,同时这本书的github链接:https://github.com/egonschiele/grokking_algorithms
这本书的第一章介绍了第一种算法——二分查找和大O表示法。大O表示法指出了算法的运行时间,算法运行时间并不以秒为单位而是从其增速的角度来衡量。在第四章中介绍了平均情况和最糟情况。
选择排序 Selection sort
数组和链表是两种基本的数据结构,本书的第二章通过选择排序来更好的理解数组。
数组在储存是必须是连续的,而链表因为使用地址指向而可以分开储存。所以,数组的读取速度很快,但插入和删除速度很慢,即如下图所示。
那么,本书的第二种算法——选择排序通过将数据从大到小或从小到大排列,运行时间即为O(n^2)。
下面是将数组元素从小到大排列的代码示例:
# 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
print(selectionSort([5, 3, 6, 2, 10]))
Output
[2, 3, 5, 6, 10]
递归recusion
“如果使用循环,程序的性能可能更高;如果使用递归,程序可能更容易理解。如何选择要看什么对你来说更重要。”
递归是一种自己调用自己的函数,它易于理解,但不一定在计算性能上有优势。编写递归函数时,必须告诉它何时停止递归。因此,递归函数的组成:基线条件(base case)和递归条件(recursive case)。倒计时函数的代码示例:
def countdown(i):
print(i)
if i<= 1: #base case
return
else: #recursive case
countdown(i-1)
栈
栈是一种数据结构,计算机在内部使用被称为调用栈(call stack)的栈。当你调用函数时,计算机用栈来表示为这个函数调用分配的一块内存。那么,当调用某个函数时还需调用其他函数的情况,如何理解栈?
- 调用其他函数时,当前函数暂停并处于未完成状态。
- 调用其他函数时,计算机为其分配一块内存位于该函数上,在函数调用返回后,栈顶的内存块被弹出。
使用栈虽然方便,但是储存详尽的信息可能占用大量的内存,如果调用递归函数但不小心导致它没完没了运行,则最后会因为栈溢出而终止。
快速排序Quicksort
示例为使用循环和递归完成累加:
#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),再在分区进行相同的操作来完成。
快速排序的代码:
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)。下图为最佳情况,也就是平均情况。
散列表Hash tables
散列表是一种包含额外逻辑的强大的数据结构,它使用散列函数来确定元素的储存位置。Python使用的散列表实现为字典。
散列表可以用于查找、防止重复、储存缓存以缓解服务器的压力。
那么,散列表是如何储存的?
它虽然模拟映射关系,但是不可能总是将不同的键映射到数组的不同位置。当遇到冲突(collision)情况,即两个键映射到了同一个位置,就在这个位置存储一个链表。所以,一个好的散列函数将极少导致冲突,使散列表的速度不会太慢。要避免冲突,需要有:
- 较低的填装因子;
- 良好的散列函数。
广度优先搜索Breadth-first search,BFS
广度优先搜索是一种用于图的查找算法,能找出两样东西之间的最短距离。
- 图由节点和边组成,用于模拟不同的东西是如何相连的。
- 广度优先搜索采用“队列(queue)”的数据结构。和栈后进先出(Last In First Out) 的数据结构相对,是一种先进先出(First In First Out) 的数据结构。
广度优先搜索的运行时间为O(人数+边数),写作O(V+E),其中V为顶点(vertice)数,E为边数。
- 拓扑排序可以穿建一个有序的任务列表;
- 树是图的子集,树是一种完全单向指向的图。
以上是该书的前半部分内容,后半部分待整理。
推荐阅读
-
《算法图解》Grokking-algorithms(上)
-
韩顺平_PHP软件工程师玩转算法公开课(第一季)01_算法重要性_五子棋算法_汉诺塔_回溯算法_学习笔记_源代码图解_PPT文档整理
-
centos7上mysql8.0rpm方式安装教程图解
-
C#七大经典排序算法系列(上)
-
百度绿萝算法更新 众多买卖链接网站摊上事了
-
Oracle 12c如何卸载?Windows7上完全卸载Oracle 12c操作步骤(图解教程)
-
centos7上mysql8.0rpm方式安装教程图解
-
如何修改Xampp服务器上的mysql密码(图解)
-
算法系列15天速成 第四天 五大经典查找【上】
-
算法系列15天速成 第七天 线性表【上】