时间复杂度估算土法

title

想必大家都知道很多算法书上面的复杂度计算基础的“第一章节”，长到你不想看。但是不看吧又觉得失去了什么。所以这篇文章就来说说这个复杂度有没有什么通俗易懂的土方法来计算。

土法一：执行一行约是一次运算

我们假设计算机运行一行基础代码，就需要进行一次运算。也就是我们常常说的 O(1)。

来写一段从 1 累加到 100 的代码：

s = 0
for i in range(1, 101):
    s += i
print(s) # 5050

如此要循环 100 次，时间复杂度就是 $O_{(100)}$ 。如此，我们改变计算上届，将 100 扩大到 n ，这样便会发现使用循环的方法进行累加是一个时间复杂度为 $O_{(n)}$ 的算法。

我们将累加算法改成等差数列前 n 项求和来计算：

s = (1 + 100) * 100 // 2 # 5050

如此，我们将一个 $O_{(n)}$ 的算法优化到了 $O_{(1)}$ 。这种优化无论是对于计算机，还是我们人脑，都可以大幅度的降低运算复杂度。

为什么说高斯是天才，因为他在小学三年级就发现了这个规律，并将一个 $O_{(n)}$ 的算法优化到了 $O_{(1)}$ 。

土法二：以经验计算时间

以前我在大学的时候参加 ACM 竞赛有这么一个土方法：

一般的计算机，在处理 $$10^7$$ 计算的时候需要消耗一秒的时间。可以写一个来验证一下：

import datetime

tot_time = 0

for t in range(0, 10):
    st = datetime.datetime.now()
    sum = 0
    for i in range(0, 10000000):
        sum += i

    ed = datetime.datetime.now()
    inv = ed - st
    tot_time += inv.microseconds / (10 ** 6)

print(tot_time / 10) 
# 0.827902s

我们发现在我的机器上 $$10^7$$ 数量级的计算在 10 次平均下是 0.827902 秒，接近一秒。

我们用搜索问题来举例

如果我们有一个有序数组 arr ，其中有 $$10^8$$ 个数字，这时候给出一数字 n ，求在这个数组中是否有这个数 n ，有则返回 true 反之 false 。我们要求在 1000ms 时间内完成。

注意最后一句，如果我们采取枚举的方案来解决这个问题，那么我们根据之前的经验来估算，需要 $\frac{10^8}{10^7} \times 1$ 也就是 10 秒。

由于是有序数组，那么我们来计算一下二分查找的复杂度：

设数组中有 N 个元素，我们一共需要查询k次，根据这两个条件我们来推导一个 K与N的通项公式（这里面，右边的式子代表在查询完k 次之后，剩余的元素个数）

f(1) = \frac{N}{2} \\ f(2) = \frac{N}{4} \\ ... \\ f(k) = \frac{N}{2^k}

由于 k 是查询的次数，也就是计算机一次运算的次数，所以我们只需要反解出 k 的值，也就是我们要求解的时间复杂度。我们假设第 k 次查询是最终态，那么说明此时剩余元素只有 1 个了。那么对于最终态的递推式就可以这样描述：

\frac{N}{2^k}=1\ \ \Rightarrow \ k=log_{2}{N}

计算完了发展度之后，我们将 N = 10^7 带入，发现 k = 26.57542 。也就是说，只需要 27 次上下的计算机运算，也就是 27 / 10^7 约是 0.0000027 秒，就可以完成查询。

所以我们如此分析，通过上限时间来推断大致的算法复杂度，获得提示确定了思路，就可以开始解题了。

土法三：取极限估算复杂度

给你一个无序数组 arr ，其中包含 n 个元素 (1 ≤ n ≤ 10^8)，另外给你一个 k (1 ≤ k ≤ n)。让你求出这个数组中的第 k 大数。要求在 1000ms 时间内完成。

看完题目第一反映，我们对 arr 数组先做一次降序排序，然后输出 arr[k] 即可。

那么我们开始使用土法二来估算时间，如果我们进行一次排序，假如是快排，那么首先我们需要一个 O(NlogN) 的复杂度来完成。然后还有一次查询，由于通过数组下标直接访问，需要 O(1) 的一次查询。

将 n 的范围右边界带入式中，由于我们知道 NlogN > N ，所以根据上面的经验，我们肯定要花费 10s 以上的时间来处理。虽然我们的想法很好，是对数组做一个预处理，然后再进行其他的算法，但实际上，由于预处理的复杂度已经远远的超过了其他计算的复杂度，也就是说我们对于一个方案的复杂度考量，往往都是在一个含操作数 N 的代数式中，当 N 取无穷大时，求每个子式子的等价无穷大，然后取最大值作为整个程序的复杂度。

拿这题为例：

f(n)=nlog_{2}n + 1 \Rightarrow {\lim_{x \to \infty}} \frac{nlog_{2}n}{1} \thicksim \infty \Rightarrow O_{(nlogn)}

可能这个还不是很明显，我们再举一个例子：

f(n)=log_{2}n!+nlog_{2}n+n+1

如果我们遇到这种表达式，我们要如何求解呢？我的土法是分成 2 部：

1. 观察后舍去差距较大的

首先，n 和 1 这两个子式显然要比前面两个都小（或者说肯定比 nlogn 要小），我们把它舍去。

\Rightarrow f'(n)=log_2n! + nlog_{2}n

2. 不确定式两两使用求极限，判断等价性

例如我们得到的 f'(n) 无法判断，那么我就取出这里面两个子式来求等价性：

\begin{aligned} &{\lim_{x \to \infty}}\frac{logn!}{nlogn} \\ =&{\lim_{x \to \infty}}\frac{log((\sqrt{2\pi n})\frac{n^n}{e^n})}{nlogn}\\ =&{\lim_{x \to \infty}}\frac{\frac{1}{2}log(2\pi) + \frac{1}{2}logn + nlogn - nloge}{nlogn} \\ =&{\lim_{x \to \infty}}(\frac{0.5log(2\pi)}{nlogn}+\frac{1}{2n}+1-\frac{1}{ln\ n})\\ =&1 \end{aligned}

所以我们发现剩下的两个式子是等价无穷大的。我们得到整体的时间复杂度：

f'(n) \Rightarrow O(nlog_2n)

所以我们可以总结出来一个规律，子式选最大，就是我们要的时间复杂度。

总结

这篇文章我们讲了：

如何结合题目的数据量来估算程序耗时，以及通过复杂度的估算来提示我们要选用什么算法；
耗时和复杂度的关系，大概就是 $$10^7$$ 为一秒；
取极限来舍去较小的子式，留下的最大子式即可作为整体算法的时间复杂度；

本作品采用 知识署名-非商业性使用-禁止演绎（BY-NC-ND） 4.0 国际许可协议 进行许可。