关于-0-到-n-中包含-1-的个数问题

40次阅读

共计 2070 个字符，预计需要花费 6 分钟才能阅读完成。

这是我偶然在网上看到的问题，它的题目原型是：

编写一个算法，统计 0 到 n 中有多少个数包含 1.

当时网上给出的算法还是比较直接的，逐步判断 0 到 n 中的数是否包含 1 即可（Python 实现）：

import math

class 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$ 时所花费的时间，得出的结果是：