Python数据结构与算法(1)基础概念

学习目标

• 了解算法和数据结构
• 算法概念
• 时间复杂度
• 空间复杂度
• 递归

了解算法和数据结构

算法是程序的灵魂，学习算法对我们学习编程有很大的帮助，算法出现的场景有很多：面试、算法比赛等，学好算法可以1.做算法相关职业，2.锻炼编程能力和逻辑思维能力，3.灵活应对求职场合。

数据结构是存储组织静态数据的方式，算法是一种处理数据的动态过程。解决不同的程序问题我们会利用到不同的数据结构来组织数据，并且选择较优的算法来处理数据。

算法概念

一个计算过程，解决问题的方法。“程序 = 数据结构 + 算法”。

时间复杂度

用一种通用的方式来体现算法运行的快慢。和时间的单位：秒、分、时等类似，算法的时间复杂度也是有O($1$)、O($n$)、O($n^2$)、O($n^3$)等单位，总的来说时间复杂度是用来估计算法运行时间的一个式子（单位），一般来说时间复杂度高的算法比时间复杂度低的算法要慢。常见的时间复杂度（按效率排序）O($1$) < O($logn$) < O($n$) < O($nlogn$) < O($n^2$) < O($n^2logn$) < O($n^3$)。

如何简单快速地判断时间复杂度？

• 第一步：确定问题的规模 —— n（如排序列表的元素，则考虑规模是列表的长度为n）。
• 第二步：遇到循环减半情况的过程 —— $logn$。
• 第三步：有几层循环，就是n的几次方，k层循环着时间复杂度为$n^k$。

空间复杂度

空间复杂度是用来体现算法内存占用大小的式子，如果问题规模n不同，这不同机器的内存占用大小也不同，所以也需要用到抽象单位来衡量空间复杂度。空间复杂度的表示方式和时间复杂度类似：

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

在通常情况下，追求时间复杂度比追求空间复杂度更重要。俗称以”空间来换时间“。

递归

递归最重要的两个条件是：调用自身+结束条件

递归在算法当中是很重要的程序组织方式，能够帮助实现一些复杂的算法。

递归的案例：汉诺塔问题

问题：三根柱子，其中一根柱子上从大到小，从低到高摞着64片黄金圆盘，要把这64片圆盘从本来摞好的柱子上转移到另一个柱子，可以借用第三根柱子。摞的方式要始终满足小的圆盘必须在大的圆盘之上，且每次只能挪动一片圆盘，求解这个问题的步骤。

将问题抽象为n个圆盘在三根柱子上的挪动，将从第一根柱子A全部挪到第三根柱子C。

• 当 n = 2 时：

  • 第一步：最小圆盘n=1从第一根柱子A移动到第二根B。
  • 第二步：把大圆盘n=2从第一根柱子A经过B移动到第三根C。
  • 第三步：把小圆盘n=1从第二根柱子B经过A移动到第三根C。

• 当为 n 时：

  • 第一步：把n-1圆盘从第一根柱子A移动到第二根B。
  • 第二步：把最底下的第n圆盘从第一根柱子A移动到第三根C。
  • 第三步：把n-1个圆盘从第二根B移回第三根C。

2个盘子挪动挪动步骤是，首先是最上面一个盘子放在缓冲区，最底下大盘移动到目标区，最后将缓冲区盘子移动到目标区；3个盘子的挪动步骤是，首先是最上面一个盘子放在目标区，第二大盘移动到缓冲区，然后将最上面盘子移动到缓冲区，将最大盘移动到目标区，再将最上面盘子移动到原位，缓冲区第二大盘子移动到目标区，原位最小盘移动到目标区。4个盘子……依次往复。

⚠️标粗位置文字描述即为（从上到下）第n-1个盘子借助缓冲区移动到目标区，标斜位置文字描述即为将最底下第n个盘子移动到目标位置，正常体位置文字描述即为将第n-1个盘子借助缓冲区还原到目标区，至此问题完成。

代码实现：

1
2
3
4
5
6
7

def hanoi(num,a,b,c):
    # 第一个参数是盘子，abc形参代表从哪根柱子，经过哪根，到哪根。
    if num>0:   # 满足条件进行递归，同时也规定了递归的结束条件
        hanoi(num-1,a,c,b)  # 把第n-1个圆盘,a经过c移动到b
        print(f"第{num}个圆盘从{a}移动到{c}")   # 把最底下的第n个圆盘从a移动到c
        hanoi(num-1,b,a,c)  # 把第n-1个圆盘从b经过a移动到c
hanoi(3,"A","B","C")

总结