无规则采集器列表算法(算法图解书籍介绍：本书示例丰富，图文并茂，大O表示法)

　　无规则采集器列表算法(算法图解书籍介绍：本书示例丰富，图文并茂，大O表示法)

　　算法图解书籍简介：本书实例丰富，图文并茂，通俗易懂地讲解算法。它旨在帮助程序员在日常项目中更好地利用算法的力量。本书的前三章将帮助您奠定基础，带您了解二分搜索、大 O 表示法、两种基本数据结构、递归等。其余篇幅将主要介绍被广泛使用的算法，包括：面对特定问题时的解决技巧，例如何时使用贪心算法或动态规划；哈希表的应用；图算法；K-最近邻算法。

　　以下是我读这本书时想起的笔记，欢迎阅读和点赞！

　　二分查找

　　在有序数组中，需要使用二分查找检查多少个元素

　　完整的实现代码如下：（注解为Python语言实现）

　　def binary_search(list,item):

low=0

high=len(list)-1

while lowitem:

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 个 Big O 运行时：

　　O(log n)，也叫对数时间，包括二分查找

　　O(n)，也称为线性时间，包括简单的查找

　　O(nx logn), quicksort - 更快的算法

　　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]sub_max else sub_max

　　C语言标准库中的函数qsort实现了快速排序，快速排序也用到了D&C。

　　快速排序步骤（1）选择一个基值

　　(2） 将数组分成两个子数组：小于基值的元素和大于基值的元素。

　　(3）快速排序这两个数组

　　【按照步骤1】以此类推，对其他数组进行快速排序

　　下面是快速排序的代码：

　　def quicksort(array):

if len(array) < 2:

return array //基线条件：为空或只包含一个元素的数组是有序的

else:

pivot = array[0] //递归条件

less = [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 实际上指的是：cxn（其中 C 是固定的时间量）。通常不考虑这个常数，因为这两种算法的大 O 运行时间是否不同并不重要。比如下面的例子：

　　简单查找：10（毫秒）xn

　　二进制搜索：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)。