算法小结(一)：递归与列表查找

一、算法的复杂度

1、如何简单快速地判断算法的时间复杂度

(1)确定问题规模n
(2)循环减半过程-->logn
(3)k层关于n的循环-->n^k

2、空间复杂度的判断

(1)算法使用了几个变量：O(1)
(2)算法使用了长度为n的一维列表：O(n)
(3)算法使用了m行n列的二维列表：O(mn)

二、递归

1、递归的两个特点

(1)调用自身
(2)结束条件

2、代码示例

def func(x):
    if x > 0:
        func(x-1)
        print(x)
func(3)
>> 1 2 3

3、汉诺塔问题

问题描述：把圆盘从下面开始按大小顺序重新摆放在另一根柱子上，要求小圆盘上面不可以放置大圆盘，在三根柱子之间一次只能移动一个圆盘。

示意图

归纳问题：
当n=2时，移动步骤为
(1)把小圆盘(1)从A移动到B
(2)把大圆盘(2-1)从A移动到C
(3)把小圆盘(2-1)从B移动到C

n=2

当有n个盘子时，移动步骤为：
(1)把n-1个圆盘从A经过C移动到B
(2)把第n个圆盘从A移动到C
(3)把n-1个小圆盘从B经过A移动到C

def hanoi(n, a, b, c):
    if n>0:
        hanoi(n-1, a, c, b)
        print("moving from %s to %s" % (a, c))
        hanoi(n-1, b, a, c)
hanoi(3, 'A', 'B', 'C')

>>moving from A to C
>>moving from A to B
>>moving from C to B
>>moving from A to C
>>moving from B to A
>>moving from B to C
>>moving from A to C

汉诺塔移动次数的递推式：h(x) = 2h(x-1)+1

三、列表查找

1、顺序查找（Python内置函数：index(x)）

循环遍历列表，从第一个元素开始，直到查找到该元素

def linear_search(data_set, value):
    for i in range(len(data_set)):
        if data_set[i] == value:
            return i
    return

print(linear_search([1,2,3,4], 2))
>> 1

2、二分查找（时间复杂度 O(logn)）

从有序列表的初始候选区开始查找，通过比较候选区中间值，可以使候选区减少一半。

def binary_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

print(binary_search([1,2,3,4], 2))
>> 1