哪个函数增长得更快：lg( √n ) vs. √ lg n？
当我进行计算时，我得到 lg (√n) 更快。它是否正确？
问问题
2007 次
3 回答
6
你的计算是正确的。lg (√n) = lg (n 1/2 ) = lg(n) / 2，增长为 (√ log n) 2
于 2012-04-09T20:14:56.790 回答
2
正如评论中提到的，如果我不确定哪一个增长得更快，我通常会绘制两个函数。通常，您会为它们绘制在预期输入范围附近的 n 值，但在这种情况下，您可以看到即使 n 的值很小，lg (√n) 也会增长得更快。
注意：上图假设lg以 2 为底， log以 10 为底。
于 2012-04-09T20:29:53.673 回答
1
你在比较
(1) lg( √n ) = lg( n ^ (1/2) ) = (1/2) * lg( n )
和
(2) √ log n = (√ lg n) / (√ lg 10)
去掉常数，剩下的就是lg( n )和√ lg n。显然，第一个增长得更快。
作为旁注，以 B 为底的 A 的对数等于以 X 为底的 A 的对数除以以 X 为底的 B 的对数，其中 X 是作为对数底的有效值。
于 2012-04-09T21:02:12.857 回答