基本概念¶

算法¶

算法（algorithm）：计算过程、解决问题的方法。

程序=数据结构+算法

时间复杂度¶

问题复杂度（问题规模）\(n\)：可以认为是一个很大的数（虽然实际上可能并不大），一个未知的数。

时间复杂度：用来评估算法运行效率的算式，是一个大概时间。如\(O(1)\)、\(O(n^2)\)。其中\(O\)可以理解为“估计”、“大约”，其中的式子表示运行效率。具体来说若括号中为\(1\)表示运行时间为一个**单位时间**，这里的单位时间是一个抽象概念。在算法中，将基本运算和打印等基本操作及其简单组合（不包括循环）的时间复杂度认为是\(1\)

例如：

例1：我们认为以下代码的时间复杂度都是\(O(1)\)

# O(1)
print("helloworld")

# 也是O(1)
print("你好世界")
a = 1
b = 1
c = a + b
print(c)

可以理解为，由于这些基本操作相对于问题复杂度\(n\)而言，实在是太小了，故将这些基本操作的时间复杂度定义为\(1\)，即一个时间单位。

例2：对于循环而言，我们看代码的时间复杂度将忽略其中的一些基本操作，重点关注其中主体部分。

# O(n^2)而不是O(n^2+n)
for i in range(n):
    print(i)
    for j in range(n)
    print(j)

例3：下面代码的时间复杂度为\(O(\log_2{n})\)，也可以省略\(2\)，简单地记作\(O(\log{n})\)（这是约定俗成的）。

while (n > 1):
    print(n)
    n /= 2

小结¶

时间复杂度仅仅是用来估计代码运行快慢的，不用作代表代码运行的具体时间长短。
一般来说，时间复杂度高的算法比时间复杂度低的代码运行速度快。（因为还需要考虑计算机本身的运行速度和问题复杂度）
常见时间复杂度效率排序：\(O(1)>O(\log n)>O(n)>O(n\log n)>O(n^2)>O(n^2 \log n)>O(n^3)\)

如何计算时间复杂度：
1. 确定问题规模n 2. 是否存在循环折半过程，若有，则存在\(log n\) 3. 若有\(k\)层关于\(n\)的循环，则存在\( n^k \) 4. 对于更复杂的情况，应当根据算法执行过程判断

空间复杂度¶

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

空间复杂度的表示方式与时间复杂度的表示方式完全相同。

例如：
- 算法使用了几个变量：\( O(1) \) - 算法使用了长度为\( n \)的一维列表：\( O(n) \) - 算法使用了\( m \times n \)的二维列表：\( O(mn) \)

“空间换时间”：用更多的内存节省计算时间。

参考资料¶

【清华计算机博士带你学习Python算法+数据结构】