数据结构与算法

程序 = 数据结构+算法

时间复杂度是用来估计算法运行时间的一个式子（单位）

一般来说(与机器与问题规模有关），时间复杂度高的算法比时间复杂度低的算法慢

常见的时间复杂度排序

O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n²logn)<O(n³)

复杂问题的时间复杂度

O(n!)

O(2ⁿ)

O(nⁿ)

判断时间复杂度

确定问题规模

循环减半过程——logn

k层关于n的循环——n^k

^{空间复杂度：用来评估算法内存占用大小的式子}

^{空间复杂度的表示方式与时间复杂度完全一样}

^{算法使用了几个变量：}O(1)

算法使用了长度为1的一维列表：O(n)

算法使用了m行n列的二维列表：O(mn)

空间换时间

1.递归

调用自身

结束条件

def fun1(n):
    if n > 0:
        print(n)
        fun1(n-1)

def fun2(n):
    if n > 0:
        fun2(n-1)
        print(n)

fun1(3)
print('-'*30)
fun2(3)

递归问题：汉诺塔问题：

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

汉诺塔移动次数递推式

h(x)=2h(x-1)+1

2.列表查找

输入：列表、待查找元素

输出：元素下标，未查找到时返回（None或者-1）

内置列表查找元素：index( )

(1)顺序查找：也叫线性查找，从列表的第一个元素开始，顺序进行搜索，直到找到元素或者搜索到列表的最后一个元素为止。

时间复杂度：O(n)

def linear_search(li,val):
    for ind,v in enumerate(li):
        if v == val:
            return ind
    else:
        return None

print(linear_search([1,2,3,4,5,6],5))

# 时间复杂度：O(n)

（2）二分查找：又叫折半查找，从有序列表的初始候选区li[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半

时间复杂度：O(logn)

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: # 待查找的值在mid左侧
            right = mid -1
        else: # li[mid] < val: # 待查找的值在mid右侧
            left = mid +1
    else:
        return None

print(binary_search([1,2,3,4,5,6,7,8,9],3))

3.排序

将一组无序的记录序列调整为有序的记录序列

列表排序：将无序列表转换为有序列表

输入：列表

输出：有序列表

升序与降序

内置排序函数：sort( )

（1）冒泡排序

默认升序排序

列表每相邻的两个数，如果前面的数比后面的大，则交换这两个数

一趟排序完成后，无序区减少一个数，有序区增加一个数

时间复杂度：O(n²)

import random
def bubble_sort(li):
    for i in range(len(li)-1): # 第几趟
        exchange = False
        for j in range(len(li)-i-1): # 每一趟的指针从0开始
            if li[j] > li[j+1]: # 箭头指的数大于后面的一个数
                li[j+1],li[j] = li[j],li[j+1]  # 则交换
                exchange = True
        print(li)
        if not exchange:
            return



# li = [random.randint(0,10000) for i in range(10)]
li = [1,2,3,4,33,5]
print(li)
bubble_sort(li)
print(li)

（2）选择排序

def select_sort_simple(li):
    li_new = []
    for i in range(len(li)):
        min_val = min(li)
        li_new.append(min_val)
        li.remove(min_val)
    return li_new

# 复杂度：O(n*n)
def select_sort(li):
    for i in range(len(li)-1): # 第几趟，第i趟的无序区的第一个数的下标是i
        min_loc = i # 假定无序区的第一个数是最小的数
        for j in range(i+1,len(li)): # 遍历无序区
            if li[j] < li[min_loc]: # 判断寻找最小的数
                min_loc = j # 找到最小的数记录最小的数的下标
        li[min_loc],li[i]  = li[i],li[min_loc] # 将找到的最小的数的下标与无序区的第一个数换位置
        print(li)


li = [22,11,2,5,56,67,88,44,55,6]
print(li)
select_sort(li)
print(li)

（3）插入排序

初始时手里只有一张牌，每次从无序区摸一张牌，插到手里已有牌的正确位置

时间复杂度：O(n²)

插入排序升序程序

def insert_sort(li):
    for i in range(1,len(li)): # i表示摸到的牌的下标，第一张牌默认为手里的牌（下标为0的位置），所以摸到的牌从1开始
        tmp = li[i] #tmp表示摸到的牌，使摸到的牌不能被覆盖
        j = i-1 # j指的就是手里的牌
        while j >= 0 and li[j] > tmp: #手里的牌为第一张或者之后并且摸到的牌比手里的小
            li[j+1] = li[j] # 将牌往右移
            j -= 1 # j从左向右遍历
        li[j+1] = tmp #摸到的牌比手里的牌大，将摸到的牌插入到比他小的牌的位置
        print(li)
#关键在于找插入位置
#区分有序区和无序区
li = [1,6,2,8,99,23,22,44,55]
print(li)
insert_sort(li)
print(li)

插入排序降序程序

def insert_sort(li):
    for i in range(1,len(li)): # i表示摸到的牌的下标，第一张牌默认为手里的牌（下标为0的位置），所以摸到的牌从1开始
        tmp = li[i] #tmp表示摸到的牌，使摸到的牌不能被覆盖
        j = i-1 # j指的就是手里的牌
        while j >= 0 and li[j] < tmp: #手里的牌为第一张或者之后并且摸到的牌比手里的小
            li[j+1] = li[j] # 将牌往右移
            j -= 1 # j从左向右遍历
        li[j+1] = tmp #摸到的牌比手里的牌大，将摸到的牌插入到比他小的牌的位置
        print(li)
#关键在于找插入位置
#区分有序区和无序区
li = [1,6,2,8,99,23,22,44,55]
print(li)
insert_sort(li)
print(li)