exam-time-complexity.md 6.2 KB

+++ date = 2019-09-13T14:50:00+08:00 draft = false tags = ["undefined-behavior", "time-complexity", "looking-for-job"] title = "Time complexity problem" summary = """ Another stupid problem can lead to some thoughts. """ authors = ["xry111"] +++

某笔试题中的时间复杂度

平时老是懒得写博客,都快一年没写了…… 又到了找工作的季节,前几天看见一道笔试题就决定写篇文章分(吐)析(槽)一下。

题目描述

如下程序实现对指定的自然数求阶乘:

int func(int n)
{
	if (n <= 1)
		return 1;
	return n * func(n - 1);
}

则其算法复杂度是:

  • A. $O(N \times \log_2 N)$
  • B. $O(1)$
  • C. $O(N^2)$
  • D. $O(N)$

这次还是把代码手工格式化了一下,不禁想吐槽那帮出题人和面试官: 学生把代码压行你们就直接骂,你们自己压行就合理合法了吗(掀桌)?

我们不去吐槽 $n$ 和 $N$ 大小写不一致的问题,也不再重复一遍 “不要用递归求阶乘”这种常识,直接试着做一下这题。容易看出, 函数 func 被递归调用 $n$ 次,而每次递归调用的时间复杂度是 $O(1)$, 故总的时间复杂度应该是 $O(n)$。看上去很简单吧,但是其实问题很多。

$O$ 与 $\Theta$ 的区别

我们首先复习一下 Big-$O$ 表示法的含义: 设 $f(x)$ 和 $g(x)$ 是两个值为正的函数,我们称

$$f(x) = O(g(x))$$

当且仅当存在常数 $N$ 和 $C$,使得

$$f(x) \leq C g(x), \forall x > N$$

如果我们假设这题的答案是 $O(n)$,不幸地,我们可以得出结论: $O(n^2)$ 也是一个合法的答案,下面我们证明之:

根据 $T(n) = O(n)$,知道存在常数 $N$、$C$,使得对于所有 $n > N$, 都有 $T(n) \leq C \cdot n$。而对于所有 $n \geq C$,都有 $n^2 \geq C \cdot n$。把不等式串联起来,得到

$$T(n) \leq C \cdot n \leq n^2 (\forall n > N, n \geq C)$$

那么我们令 $N' = \max (N, C+1), C' = 1$,就有

$$T(n) \leq C' \cdot n^2 (\forall n > N')$$

因此这题也能选 $O(n^2)$。同理,$O(n \log_2 n)$ 也是可以选的。

为什么我们在平时做题或者写题解的时候可以使用 Big-$O$ 表示法呢? 这是因为我们只要分析时间复杂度的渐进上界, 就能基本看出这算法能不能在题目的时间限制内跑完。 例如 $n = 1000$ 时,我们只要能够证明时间复杂度是 $O(n^2)$, 基本就敢写程序了。至于它其实可不可能是 $O(n \log n)$ 或者甚至 $O(1)$ 我们并不用去证明。但是,对于一道单项选择题来说, 只有使用 Big-$\Theta$ 表示法才是正确的。$f(x) = \Theta(g(x))$ 意味着 $f(x) = O(g(x))$,且 $g(x) = O(f(x))$, 这样就不会陷入选了一个复杂度,结果更高复杂度都能选的尴尬境地。

下文假设选项都使用了 Big-$\Theta$ 符号。

未定义行为可能导致出人意料的结果

我们之前已经无数次讨论未定义行为,稍有常识的人都能看出, 对于本题提供的代码,只要 $N$ 稍大,就会触发带符号整数溢出这一未定义行为。 例如,在一台 int 为 32 位带符号整数类型的机器上,打开 gcc-fsanitize=undefined 开关,编译并运行该程序:

test.c:15:11: runtime error: signed integer overflow: 13 * 479001600 cannot be represented in type 'int'

需要注意的是,未定义行为属于一种编程错误。那么,只有两种可能:

  • 这题的题面是错的,应该改成“如下程序在 x86_64-Linux 平台实现对 $12$ 以内的自然数求阶乘”。那么因为 $12$ 是个常数,答案应该是 $\Theta(1)$。
  • 这题的代码是错的。那这显而易见地体现了贵司拙劣的代码水平,还招个 p 人啊。

就算我们不考虑代码错误的问题,未定义行为就是 “什么都可能发生,也可能什么都不发生”,那么这程序在 $n > 12$ 时可以跑任意长时间,甚至不会终止,那么就没有选项可以选了。

代码优化可能导致出人意料的结果

当然,一些项目使用 -fwrapv 保证带符号整数溢出具有确定(2-补码)的行为, 例如 Linux 内核。为了让这题看上去可做一点,我们假设使用了该选项。 那么如果我是一个 C 编译器,我会怎么分析这代码呢?补码算术相当于对 $2^{32}$ 取模,那么如果一堆数中质因子 $2$ 出现的总次数达到 $32$, 则它们乘起来以后模 $2^{32}$ 肯定是 $0$。因此,

$$64! \equiv 0, \mod 2^{32}$$

(这只是一个粗糙的界,实际上 $34!$ 已经余 $0$ 了。)

于是,作为一个聪明的编译器,我决定把代码优化成

int func(int x)
{
	static const int ans[] = {1,1,2,6,24,/*...*/};
	unsigned t = x & 0xFFFFFFC0u;
	return t ?t >> 31 : ans[x];
}

这样时间复杂度就变成了 $\Theta(1)$。

从以上分析我们可以看出,在讨论算法时间复杂度的问题时, 根本不该 出现任何编程语言编写的代码。 这是因为编程语言只规定了代码产生的副作用 (side-effect) 或其行为, 只要能够保证行为一致,编译器可以把实际的目标代码优化到他妈都不认识, 导致时间复杂度变化。此时我们必须使用严谨的数学语言。

计算机字长与时间复杂度

如果这个题给出了伪代码(而不是 C 代码),并且声明了计算机字长足够大, 那么可以说时间复杂度是 $\Theta(n)$。不幸的是, 现实中计算机的字长往往很小,此时时间复杂度该如何计算呢?

首先我们需要使用斯特林近似,求出阶乘的计算机表示需要多少个字:

$$s = \log_W n! \approx \log_W \left( \sqrt{2 \pi n} \left( \frac{n}{e} \right)^n \right)$$

随便把对数变换一下,就能看出

$$s = \Theta(n \log n)$$

计算 $n \times (n-1)!$ 的时间复杂度就是

$$T_1(n) = \Theta(n (\log n)^2)$$

对它求和就能得到总的时间复杂度 $T(n) = \sum_i T_1(i)$。 这个和很难求,但反正我们只关心渐进复杂度,此时可以用积分代替求和:

$$T(n) = \Theta\left(\int_1^n n (\log n)^2 dn \right)$$

连用两次分部积分法得到

$$T(n) = \frac{1}{2} \Theta((n \log n)^2) - \frac{1}{2} \Theta(n^2 \log n) + \frac{1}{4} \Theta(n^2)$$

去掉低阶项和常数,就是 $T(n) = \Theta((n \log n)^2)$。