这是我偶然在网上看到的问题，它的题目原型是：
编写一个算法，统计 0 到 n 中有多少个数包含 1.
当时网上给出的算法还是比较直接的，逐步判断 0 到 n 中的数是否包含 1 即可（Python 实现）：
import mathclass AlgorithmOne: def count_ones(self, n): count = 0 for i in range(0, n+1): if (self.contains_one(i)): count = count + 1 return count def contains_one(self, n): while n > 0: if n % 10 == 1: return True else: n = math.floor(n / 10) return False我这里将算法包含在AlgorithmOne内，是因为我将在下面给出另外的解法，它的算法复杂度更低。AlgorithmOne的算法复杂度为$O(n\lg n)$：在count_ones内有 n 个循环，每个循环都包含一个contains_one的调用。而每个contains_one最多包含$\lg n$次while循环。
实际上，给定一个 n 值，我们可以直接计算出包含 1 的数字个数。例如 n=99，0 到 99 当中包含 1 的数字有它的规律：1）个位数是1，如 1、11、21、……、91；2）十位数是1，如10、11、12、……、19.
基于此，我设计了如下的算法：
class AlgorithmTwo: def count_ones(self, n): if (n == 0): return 0 # 计算 n 的首位数和一共的位数 x, k = self.calc_parts(n) # 计算 0 到 (x-1)99 一共有多少个数带 1 count = 0 for i in range(0, x): # 计算 i00 到 i99，其中 i 有可能为 0 if i == 1: count += 10 ** (k-1) else: count += self.count_0_to_xxx(k - 1) # 计算剩下的数 left_part = n - x * (10 ** (k-1)) if x == 1: count += left_part + 1 else: count += self.count_ones(left_part) return count # 0..xxx(k位)有多少个数带 1 def count_0_to_xxx(self, k): count = 0 for i in range(1, k+1): count += self.count_1xx_to_xxx(i) return count # 1xx..xxx(k位)有多少个数带 1 def count_1xx_to_xxx(self, k): total = 9 * (10 ** (k-1)) excluded = 8 * (9 ** (k-1)) return total - excluded # 提取一个数的首位数和它的位数 def calc_parts(self, n): k = 1 while n >= 10: k += 1 n = math.floor(n / 10) return (n, k)很明显，整个算法的复杂性增加了，但它的复杂度显著降低了。
在分析主函数count_ones的复杂度之前，我们先分析count_0_to_xxx的复杂度。我们看到，在count_0_to_xxx中一共有 k 次count_1xx_to_xxx的调用，而每次count_1xx_to_xxx都是常亮时间的，所以count_0_to_xxx的复杂度是$O(k)$. 如果 k 是 n 的位数，则算法复杂度可以表示为$O(\lg n)$.
在count_ones中，我用典型的注释划分了这个函数的逻辑，这样也方便我们分析算法的复杂度：
- 计算 n 的首位数和一共的位数：这一步用到
calc_parts，类似于AlgorithmOne.contains_one，复杂度为$O(\lg n)$. - 计算 0 到 (x-1)99 一共有多少个数带 1：这一步一共有 x 次
count_0_to_xxx的调用。因为 x 是 n 的首位数字，它总是一个小于 10 的数，所以这一部分的复杂度与count_0_to_xxx相同，即$\lg n$. - 计算剩下的数：最后是 n 去掉首位数字之后的递归调用。因为是个尾递归，我们可以理解为
count_ones一共调用了$\lg n$次(即 n 的位数）。将它再乘以每次调用所消耗的时间，得出总的复杂度为$O(\lg n \times \lg n)$，即$O(\lg^2 n)$.
通过分析得知，我们得出两种算法的复杂度，一个为$O(n\lg n)$，另一个是$O(\lg^2 n)$. 这是什么意思呢？这意味着算法二的复杂度远远小于算法一的复杂度。由于$\lg n$是一种渐进性很低的函数，它几乎等效于常量时间，所以无论 n 多大，算法二都能很快地得出结果，而算法一对于太大的 n 值就有点吃紧了。
我在我的电脑上，粗略地测试了一下两个方法在 $n=10^7$ 时所花费的时间，得出的结果是：
- 算法一：28 秒
- 算法二：1 秒不到
后记：这道题曾经被我拿做我们公司招聘时的笔试题。但不知为何，无论之前或之后我和应聘者聊得多欢，一遇到算法相关的部分对方就卡壳了，甚至给出算法一的自然解法都不利索。怎么说呢，谨希望通过这篇文章能够让你爱上算法。