如何证明lg n,ln n,log2 n的时间复杂度一样?

kofii · 发表于 2020-11-30 22:33

本帖最后由 kofii 于 2020-11-30 23:15 编辑

如何证明lg n,ln n,log2 n的时间复杂度一样?

沉默之剑 · 发表于 2020-11-30 23:11

换底公式：log_a(b) = log_c(b)/log_c(a)
以前两个为例：lg(n) = log_10(n) = log_e(n)/log_e(10) = ln(n)/ln(10)
也就是说，lg(n)和ln(n)的差距只在于系数

kofii · 发表于 2020-11-30 23:15

沉默之剑发表于 2020-11-30 23:11
换底公式：log_a(b) = log_c(b)/log_c(a)
以前两个为例：lg(n) = log_10(n) = log_e(n)/log_e(10) = ln(n) ...

恍然大悟，谢谢老哥

lowellddh · 发表于 2020-12-1 00:05

沉默之剑发表于 2020-11-30 23:11
换底公式：log_a(b) = log_c(b)/log_c(a)
以前两个为例：lg(n) = log_10(n) = log_e(n)/log_e(10) = ln(n) ...

正解啊，仁兄！！！

行则将至 · 发表于 2020-12-1 07:46

时间复杂度是什么东西，这不是对数函数吗？我一脸懵

帐号		自动登录	找回密码
密码			注册[Register]

[已解决] 如何证明lg n,ln n,log2 n的时间复杂度一样?