Python 数据结构和算法 03| 大 O 表示法的 Python 代码示例

在前一篇中，相信你对大O表示代码复杂度的方法有了一定的了解了，接下来小帅b会继续跟你说一下这些常用表示方法对应的 Python 代码示例，让你之后能够更加清晰的去分析某一段的代码复杂度。

通往 Python 高手之路

大 O 表示法的 Python 简单代码示例

我们一般在写的代码，没一行会执行一次，是常数级别的，比如这样：

这样是不是执行了 4 次，所以说这段代码的复杂度是 O(4) , 又由于代码的复杂度表示的是随着代码的增速和代码执行次数的关系，所以这时候 O(4) 就可以直接表示为 O(1)，只要次数不是到达 n 的规模，我们都会把这种运行常数量级别的代码表示为 O(1), 比如这个：

尽管代码执行了 100000 次， O(100000) 也是用 O(1) 来表示。

而代码的执行次数达到了 n 的级别，我们才使用 O(n) 来表示它：

看这种嵌套循环的代码：

在第一层循环的时候，复杂度是 O(n) , 但每一次循环又做了 n 次循环，所以这段代码的复杂度是 O(n*n), 也就是 O(n²)。

我们来看这段代码：

你觉得输出的是多少呢？

这里我们用到了 while 循环，只要发现 sum < n , 就让它 * 2，直到 sum >= n 的时候跳出循环，那么需要执行多少次呢？

因为每次都是 * 2 ，那么应该是这样的：

2 的（执行次数）的次方 = n

通过 log 就可以这样表示：

执行次数 = log(n)

所以这段代码的复杂度就是 O(logN)

那么把上面这段代码执行 n 次, 复杂度就是 n*log(n) 了：

本文隐藏内容登陆后才可以浏览

但其实，代码的复杂度要描述的是增速，和次数无关，所以我们只需要关注最复杂的就可以了，也就是说，上述那两个的复杂度只要这样表示就可以了：

O(3+n) = O(n)
O(3+n²+n) = O(n²)

ok, 以上的原理，同样适用于空间复杂度的分析，下一篇再见！