客户端几乎不用的算法系列：复杂度估算的土方法

用户2932962

发布于 2019-12-11 14:36:22

7170

发布于 2019-12-11 14:36:22

文章被收录于专栏：程序员维他命

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

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

我们假设计算机运行一段基础代码，就需要进行一次运算。也就是我们常常说的 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)。

土法二：以经验计算时间

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

一般的计算机，在处理 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 时间内完成。

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

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

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

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

计算完了发展度之后，我们将 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 取无穷大时，求每个子式子的等价无穷大，然后取最大值作为整个程序的复杂度。

拿这题为例：