给出的选项:
(a) O(2N)
(b) O(N)
(c) O(logN)
(d) O(n^2)
我在网上考试中遇到过这道题。他们提到的正确选项是 O(logN)。但是在我看来应该是O(2N),因为他们给出的“n^2”,“n”是小写的,否则应该是O(N^2)。有人帮我找到正确的答案。
最佳答案
要比较复杂度 O(A(n))
和 O(B(n))
,您应该计算极限:
lim A(n)/B(n) = ?
n->+Inf
您可以有三种可能的结果:
0 A (infinitely) faster than B
+Inf A (infinitely) slower than B
v > 0 A~B; A is v times slower than B
在你的情况下:
lim(n^2/2n) = lim(n^2/n) = lim(n^2/log(n)) = +Inf
n->+Inf n->+Inf n->+Inf
这就是为什么 (d) O(n^2)
是(a)..(d)
算法中最慢 的算法。
最快 算法是(c) O(log(n))
,(使用L'Hospital's rule 计算极限):
lim(log(n)/2n) = lim(log(n)/n) = lim(log(n)/n^2) = 0
n->+Inf n->+Inf n->+Inf
最后,算法从最快到最慢排序:
(c) O(log(n)), (b) O(n), (a) O(2*n), (d) O(n^2)
关于algorithm - 给出了三种算法的时间复杂度。对于大的 N 值,哪个应该执行最慢?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44143065/