算法基础——列表查找

what's the 算法

　　算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

　　算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。

时间复杂度

　　时间复杂度用于评估算法运行效率。

　　在计算机科学中，算法的时间复杂度是一个函数，它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。通常写法为O(n)

举例说明：

print('Hello World')               #O(1)  只执行一次


for i in range(n):    
    print('Hello World')           #O(n)   执行了n次
 
for i in range(n):    
    for j in range(n):        
        print('Hello World')       #O(n**2)   执行了n*n次
    
for i in range(n):    
    for j in range(n):        
        for k in range(n):            
            print('Hello World')   #O(n**3)   执行了n*n*n次

while n > 1:    
    print(n)    
        n = n // 2
"""
n=64时输出：

64
32
16
8
4
2   所以我们发现这个执行的次数是2的幂次方，O(log2 n)简写为O(logn)
"""

注意：时间复杂度没有O(3)、O(1/2n)、O(n^2+n)的说法，因为时间复杂度只是一个用于衡量的估算值，所以上述改写为O(1)、O(n)、O(n^2)即可

　　一般来说，时间复杂度高的算法比时间复杂度低的算法效率要慢，常见的时间复杂度按效率排序为：

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^2*logn) < O(n^3)

　　当然还有一些不常用的时间复杂度——O(n!) O(2^n) O(n^n) …这些都不重要

空间复杂度

　　空间复杂度(Space Complexity)用来评估算法内存占用大小的一个式子。

　　空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

　　一般小程序的情况下，我们通常会稍微牺牲点内存来加快效率，即我们会用空间换时间，所以我们会适当提高空间复杂度以减少时间复杂度。

列表查找

算法最基本的应用就是对列表的查找与排序，这里我们说一下列表查找。

列表查找就是针对一个列表中待查找的元素，输出该元素的索引值index，如果该列表中不含有目标值则输出None

列表查找的方式有两种——顺序查找与二分查找

- 顺序查找：从列表第一个元素开始，顺序进行搜索，直到找到为止。
- 二分查找：从有序列表的候选区data[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半。

li=[1,2,3,4,5,6,7,8,9,10]

#顺序查找
def linear_search(data_set, value):
    for i in data_set:
        if data_set[i] == value:
            return i
    return

the_index=linear_search(li,3)
print(the_index)#2     O(n)

#二分查找
def bin_search(data_set, value):
    low = 0
    high = len(data_set) - 1
    while low <= high:
        mid = (low+high)//2
        if data_set[mid] == value:
            return mid
        elif data_set[mid] > value:
            high = mid - 1
        else:
            low = mid + 1

bin_index=bin_search(li,3)
print(bin_index)#2    O(logn)       可以发现二分查找比顺序查找要更快

二分法可使用递归完善：

def bin_search_rec(data_set,value,low,high):
    if low <= high:
        mid=(low+high) // 2
        if data_set[mid] == value:
            return mid
        elif data_set[mid] > value:
            return bin_search_rec(data_set,value,low,mid-1)
        else:
            return bin_search_rec(data_set,value,mid+1,high)
    else:return None

li=[1,2,3,4,5,6,7,8,9,10]
a=bin_search_rec(li,3,1,10)
print(a)#2

使用递归的二分法

列表查找小练习：

　　现有一个学员信息列表（按id增序排列），格式为：

　　　　[ {id:1001, name:"张三", age:20}, {id:1002, name:"李四", age:25}, {id:1004, name:"王五", age:23}, {id:1007, name:"赵六", age:33} ]

　　修改二分查找代码，输入学生id，输出该学生在列表中的下标，并输出完整学生信息。

列表排序

列表排序即将无需列表变为有序，Python的内置函数为sort()。应用的场景主要有：各种榜单、各种表格、给二分查找用、其他算法用等等。

有关列表排序的算法有很多，主要分为：

low B三人组：冒泡排序、选择排序、插入排序
NB三人组：快速排序、堆排序、归并排序
其他排序算法：基数排序、希尔排序、桶排序

有关列表排序算法博客链接地址：http://www.cnblogs.com/zhuminghui/p/8401129.html