算法图解1-2/11

原书作者 Aditya Bhargava

1 算法简介

1.1 二分法查找

二分法查找，正是猜数字游戏的玩法：A从1-100中随机挑一个数，B来猜，A返回B猜的数是大了还是小了，最快的一种方法就是二分法（猜50-->小了，接下来猜75……）

二分法查找速度.png

def binary_search(list, item):
  low = 0
  high = len(list)-1
  while low <= high:
    mid = int(round((low + high)/2))  #←---就检查中间的元素
    guess = list[mid]
    print(guess)
    if guess == item:  #←--------找到了元素
       return mid
    if guess > item:
        print('←-------------猜的数字大了')   
        high = mid - 1
    else:
        print('←--------------猜的数字小了')
        low = mid + 1
  return None  #←--------------------没有指定的元素

#测试
my_list = [1, 3, 5, 7, 9]  
print(binary_search(my_list, 3))

1.2 算法运行时间

不同的算法，运行时间差异很大。

简单查找与二分查找.png

五种最常见的算法运行时间

• O(logn)，也叫对数时间，如二分查找。
• O(n)，也叫线性时间，如简单查找。
• O(n * logn)，如快速排序(后续笔记)
• O(n^2)，选择排序（后续笔记）——一种速度较慢的排序算法。
• O(n!)，如旅行商问题。

image.png

2 选择排序

2.1 数组和链表

数组就是一列相邻的数据，位置关系固定，查找(读取很快)，要插入1个数据时，必需把后面的数据全部移动一位；但如果内存中的连续空位不够时就比较麻烦；
链表中中每个元素会记录下一个元素的位置，所以插入很好操作——只需修改一个指向记录。删除操作类似的，也只需要更改某下一个元素的指向位置即可。

• 计算机内存犹如一大堆抽屉。
• 需要存储多个元素时，可使用数组或链表。
• 数组的元素都在一起。
• 链表的元素是分开的，链表中的元素可存储在内存的任何地方，其中每个元素都存储了下一个元素的地址。
• 数组的读取速度很快。
• 链表的插入和删除速度很快。

image.png

2.2 选择排序

选择排序：遍历这个列表，找出播放次数最多的乐队，并将该乐队添加到一个新列表中。接下来继续该操作(找到第二多的乐队)，最终得到一个有序列表。

从大到小排序-选择排序

每次操作需要针对剩余的n个元素(n,n-1,……1，平均为n1/2)，共操作n次，故算法时间为O(nn*1/2)，通常忽略常数项，得算法时间为O(n^2)