《算法（第四版）》算法分析章节中的近似

[Higurashi]

《算法（第四版）》“1.4 算法分析”中的“1.4.3.1 近似”部分有这样一段文字（^^ 中的部分为上标）：

“一般我们用到的近似方式都是 g （ N ）～ af （ N ），其中 f （ N ）=N^b^（ logN ）^c^，其中 a 、b 和 c 均为常数。我们将 f （ N ）称为 g （ N ）的增长的数量级。我们一般不会指定底数，因为常数 a 能够弥补这些细节。”

我不理解，这里的“一般不会指定底数，因为常数 a 能够弥补这些细节”是什么意思？省略底数难道不会对对数的图像有着比较明显的影响吗？为什么说“常数 a 能够弥补这些细节”？

任何想法或建议都可能是有帮助的。谢谢。

[o02VFqu3gZnZfX8n]

1. 是对数的换底，log(N) 以 2 为底，以 10 为底，结果差距是常数，和 N 无关，可以把这一部分计算到 a 里面
2. 对图像有影响，但是这种影响相对于 N 的变化来说，可以忽略

你可以接着往下看，为什么最后可以简单用 N^3 来表示了

[Higurashi]

@DaVinci42 #1 我懂了，非常感谢。有一个疑问是，对于一个增长数量级为 log10N 的算法，通过换底，其增长数量级也可以是 log2N ，我理解的增长的数量级，主要是用来反映算法时间成本的增长快慢（根据其图像的形状），而现在从图上看，log10N 和 log2N 的增长快慢差别似乎比较明显，或许该用来形容不同的算法，在这时候，如何理解“影响相对于 N 的变化来说，可以忽略”？

[Higurashi]

@Higurashi #2 我想我知道了。当数据量很大时，log10N 和 log2N 之间的差别其实并不“显著”（可以到 https://www.geogebra.org/graphing?lang=zh_CN 看看），也正因如此，只有一个“对数级别”而不存在所谓“log10N 级别”或是“log2N 级别”。

[ikesnowy]

@Higurashi

对于你的例子（两个都是对数级别的），换底之后常数 a 的变化抵消了底数的变化，最后图像是不会因为换底而变化的。

g(N)=log10(N)=1/log2(10) * log2(N)=af(N), a=1/log2(10), f(N)=log2(N)

近似（~）去掉的是小项（也就是保留增长速度最快的一项），增长的数量级则是进一步去掉系数 a （参考大 O 符号）。

[Higurashi]

@ikesnowy #4 嗯，是。所以看来增长的数量级可用来给时间成本的增长快慢分类，比如两种不同的对数增长都属于对数级别、两种不同的线型级别也同属于线性级别（即使两者之间有比较明显的快慢区分）。也正因为如此，增长数量级相对于近似来说更“粗糙”，作者也在答疑中回复道：
“我们希望讨论的是给定成本模型下所有语句执行的准确频率，因为它们能够提供更多关于算法性能的信息，而且从我们所讨论的算法中获取这些频率是可能的。例如，我们可以说‘ThreeSum 访问数组的次数为～ N^3/2’，以及‘在最坏情况下 cnt++执行的次数为～ N^3/6’，它们虽然有些冗长但给出的信息比‘ThreeSum 的运行时间为 O （ N^3 ）’要多得多。”