算法（AlogIthm）：一个计算过程，解决问题得方法。

程序=数据结构+算法

变量、列表、字典，我们成为数据，如i=1, 数据是不变得，怎么让数据变动，修改的过程是一个算法。
算法有输入有输出，封装是一个函数，函数有入参出参。

算法期望解决一类公共问题的抽象。

时间复杂度

image.png

  • 用什么方法体现算法运行的快慢？

    时间？ 机器性能不同。 问题的规模不确定：比方说上面的n

时间复杂度：
O： 数学商街的一个东西，我们可以理解为大约。
如O（1），1代表一次运行的单位。

通过类似公式，形象的看哪些算法比较快，哪么慢

image.png

注意：我们说的O（1）中1是单位。就像生活中，我们不会说我烧水要三个1分钟，我睡觉睡了7个小时12分钟。
image.png
我们强调的是一个大概的时间表示。
image.png

每次循环，问题的规模减少为1半。这个时候就会出现logN

总结

  • 时间复杂度是用来估算运行时间的一个式子（单位）
  • 一般来说，时间复杂度高的算法比时间复杂度低的算法慢

  • 常见的时间复杂度排序：

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

  • 复杂问题的时间复杂度

    O(n!) O(2^n) O(n^n)

如何简单快速的判断算法复杂度

  • 快速判断算法复杂度（适用绝大多数简单情况）

    确定问题规模n 循环减半过程 -> logn k层关于N的循环 -> n^k

  • 算法情况：根据算法执行过程判断。

    空间复杂度

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

    主要还是涉及n的问题

空间复杂度的表示方式和时间复杂度完全一样：

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

空间换时间，一般时间比空间重要。