算法是人们利用电脑解决问题的技巧。《图解算法》这本书以轻松的对话方式,采用图解的辅助说明,帮助读者简单、自然地掌握算法的基本概念,并养成主动思考的习惯,达到用算法解决实际问题的目的。本书豆瓣评分高达8.4,建议要学习算法的同学可以先看这本书入门。
《算法图解》豆瓣评分
全书共分12章,内容包括一切从观察开始、分而治之法、动态规划、贪婪法、修剪与搜索法、树搜索法、问题转换、图算法、计算几何、算法的难题、逼近算法、随机算法等。 本书示例丰富,图文并茂,以易于理解的方式阐释算法,帮助程序员在日常项目开发中更好地发挥算法的能量。我把我从这本书学到的知识内容整理为几篇笔记,希望对你们有帮助。
二分法查找
在有序的数组中,用二分法查找需要检查多少个元素
完整实现代码如下:(笔记都是Python语言实现)
def binary_search(list,item):
low=0
high=len(list)-1
while low<=high:
mid=(low+high)/2
guess=list[mid]
if guess==item:
return mid
if guess>item:
high=mid-1
else :
low=mid+1
return None #没有指定的元素
my_list=[1,3,5,7,9]
print(binary_search(my_list,3) #=>1 第二个位置的索引为1
print(binary_search(my_list,-1) #=>None 没有找到指定的元素
大O表示法
该算法指出了算法有多快。大O表示法指的并非以秒为单位的速度,而是比较操作数,指出算法运行时间的增速。大O算法一般运行时间都省略常数,+、-、乘除也都省略。
二分法使用大O表示法表示运行时间为O(log n)。
下面从快到慢的顺序列出了15种大O运行时间:
O(log n),也叫对数时间,包括二分查找
O(n),也叫线性时间,包括简单查找
O(n x logn),快速排序法—速度较快的算法
O(n^2),选择排序——一种速度较慢的算法
O(n!),旅行商问题的解决方法——非常慢的算法
选择排序
数组:所有数组在内存中都是相连的(紧靠在一起)。如果·计算机预留内存不够,就得转移到其它内存去。一般计算机都会预留比较多的内存已让其它数组存进来,但是这也是对内存的一种浪费。
链表:链表的每一个元素都储存了下一个元素的地址,从而使一系列随机的内存地址串在一起。所以在链表添加元素很容易,只需将其放入内存,并将其地址储存在前一个元素中。
所以链表读取速度慢,但是插入速度快;数组插入速度慢。
下面是常见数组和链表操作的运行时间
| |数组 |链表 |
| 读取 | O(1) | O(n)|
| 插入 |O(n) |O(1) |
|删除 |O(n) |O(1) |
数组一般用的比较多,因为它支持随机访问和顺序访问;而链表只能顺序访问,因此经常说数组的读取速度很快。
示例代码:
#查找最小值的函数
def findSmalllest(arr):
smallest=arr[0] #储存最小的值
smallest_index=0 #储存最小元素的索引
for i in range(1,len(arr)):
if arr[i]<smallest:
smallest=arr[i]
smallest_index=i
#对数组进行排序
def selectionSort(arr):
newArr=[]
for i in range(len(arr)):
smallest=findSmallest(arr)
newArr.append(arr.pop(smallest)
return newArr
print(selectionSort([5,3,6,2,10]))
递归
每个函数都有两部分:基线条件和递归条件。递归条件指的是函数调用自己,而基线条件指的是函数不再调用自己,从而避免形成无限循环。如下述伪代码所示:
def countdown(i):
print(i)
if (i<=1): //基线条件
return
else: //递归条件
countdown(i-1)
快速排序
你有可能会遇到使用任何已知的算法都无法解决的问题,优秀的人一般都不会放弃,分而治之(D&C)【divide and conquer】是你学习的第一种通用的问题的解决方法。
提示:编写涉及数组的递归函数时,基线条件通常是数组为空或只包含一个元素。陷入困境时,请检查基线条件是不是这样的。
例如:请编写一个递归函数来计算列表包含的元素数。
def count(list):
if list==[]:
return 0
else:
return 1+count(list[1:])
找出列表中最大的数字:
def max(list):
if len(list)==2:
return list[0] if list[0]>list[1] else list[1]
sub_max=max(list[1:])
return list[0] if list[0]>sub_max else sub_max
C语言标准库中的函数qsort 实现的就是快速排序,快速排序也使用了D&C。
快速排序步骤
(1)选择一个基准值
(2)将数组分为两个子数组:小于基准值的元素和大于基准值的元素。
(3)对这两个数组进行快速排序【按步骤一来】
以此类推,对其它数组都进行快速排序
下面是快速排序的代码:
def quicksort(array):
if len(array) < 2:
return array //基线条件:为空或只包含一个元素的数组是有序的
else:
pivot = array[0] //递归条件
less = [i for i in array[1:] if i <= pivot //由小于或等于基准值的元素组成的子数组
greater = [i for i in array[1:] if i > pivot] //由所有大于基准值的元素组成的子数组
return quicksort(less) + [pivot] + quicksort(greater)
print(quicksort([10,5,2,3]))
在大O表示法O(n)中,n实际上指的是这样的:c x n(其中C为固定的时间量)。通常不考虑这个常量,因为如果两种算法的大O运行时间不同,这种常量将无关紧要。如下面这个例子:
简单查找:10(毫秒)x n
二分查找:1(秒)x logn
如上述所示,你可能认为简单查找的速度要快于二分查找,然而实际上二分查找要速度快得多。所以常量根本没有什么影响。
在这实例中,层数为O(log n)用技术术语来说,调用栈的高度为O(log n),而每层需要的时间为O(n)。因此整个算法需要的时间为O(n)xO(log n)=O(nlog n)。
在最糟的情况下,有O(n)层,因此该算法的运行时间为O(n)xO(n)=O(n^2)。