nlgn 与 n 的平方执行效率比较
目录
本题为《算法4》作者 Robert Sedgewick 和 Kevin Wayne 在 Cursera 上开设的公开课的习题解答,本题为WEEK1中第二部分视频中的选择题。地址为:
https://www.coursera.org/learn/algorithms-part1/lecture/xaxyP/analysis-of-algorithms-introduction
原题
Suppose that n equals 1 million. Approximately how much faster is an algorithm that
performs nlgn operations versus one that performs n² operations?Recall that lg is base-2
logarithm function.
A 20X
B 1,000X
C 50,000X
D 1,000,000X
读题
假设 n 等于1百万,执行 nlgn 操作相对于执行 n 的平方操作大约快了多少?回想一下 lg 是以2为底的对数函数。
解题
-
在读懂题目意思的前提下,就是一到很简单的计算题了。
-
使用公式可得结果 $\frac{1000000^2}{1000000 \cdot log_{2}1000000} \approx \frac{1000000}{20} = 50000$