Python数据结构与算法1

1.时间复杂度的简单判断：

a.确定问题规模  n

b.循环减半过程->logn

c.k层关于n的循环->n*k

o(1)

时间复杂度高的算法比复杂度低的算法慢

2.递归：

汉罗塔问题：

思路：有n个盘子，从a经过b移到c，

如果还有盘子，把上面的n-1个盘子从a进过c再到b,

再把第n个盘子从a移到c

再把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')

 3.查找：

列表查找：从列表中查找元素

顺序查找（线性查找):从第一个查找到最后一个

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

二分查找：一折为二进行查找

def binary_search(li,val):
    left=0
    right=len(li)-1
    while left<=right:
        mid=(left+right)//2
        if li[mid]==val:
            return mid
        elif li[mid]>val:
            right=mid-1
        else :
            left=mid+1
    else:
        return None

         注意：二分查找复杂度为O(logn);顺序查找复杂度为O(n);所以二分查找更快，但是它的使用前提是列表已经排好了序。