+++ 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)$。

exam-time-complexity.md 6.2 KB History Raw