《算法(第四版)》算法分析章节中的近似

2022-02-08 10:19:06 +08:00
 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 能够弥补这些细节”?

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

1156 次点击
所在节点    问与答
5 条回复
o02VFqu3gZnZfX8n
2022-02-08 11:37:40 +08:00
1. 是对数的换底,log(N) 以 2 为底,以 10 为底,结果差距是常数,和 N 无关,可以把这一部分计算到 a 里面
2. 对图像有影响,但是这种影响相对于 N 的变化来说,可以忽略

你可以接着往下看,为什么最后可以简单用 N^3 来表示了
Higurashi
2022-02-08 11:57:52 +08:00
@DaVinci42 #1 我懂了,非常感谢。有一个疑问是,对于一个增长数量级为 log10N 的算法,通过换底,其增长数量级也可以是 log2N ,我理解的增长的数量级,主要是用来反映算法时间成本的增长快慢(根据其图像的形状),而现在从图上看,log10N 和 log2N 的增长快慢差别似乎比较明显,或许该用来形容不同的算法,在这时候,如何理解“影响相对于 N 的变化来说,可以忽略”?
Higurashi
2022-02-08 14:33:51 +08:00
@Higurashi #2 我想我知道了。当数据量很大时,log10N 和 log2N 之间的差别其实并不“显著”(可以到 https://www.geogebra.org/graphing?lang=zh_CN 看看),也正因如此,只有一个“对数级别”而不存在所谓“log10N 级别”或是“log2N 级别”。
ikesnowy
2022-02-08 14:43:20 +08:00
@Higurashi

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

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

近似(~)去掉的是小项(也就是保留增长速度最快的一项),增长的数量级则是进一步去掉系数 a (参考大 O 符号)。
Higurashi
2022-02-08 14:55:56 +08:00
@ikesnowy #4 嗯,是。所以看来增长的数量级可用来给时间成本的增长快慢分类,比如两种不同的对数增长都属于对数级别、两种不同的线型级别也同属于线性级别(即使两者之间有比较明显的快慢区分)。也正因为如此,增长数量级相对于近似来说更“粗糙”,作者也在答疑中回复道:
“我们希望讨论的是给定成本模型下所有语句执行的准确频率,因为它们能够提供更多关于算法性能的信息,而且从我们所讨论的算法中获取这些频率是可能的。例如,我们可以说‘ThreeSum 访问数组的次数为~ N^3/2’,以及‘在最坏情况下 cnt++执行的次数为~ N^3/6’,它们虽然有些冗长但给出的信息比‘ThreeSum 的运行时间为 O ( N^3 )’要多得多。”

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/832373

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX