algorithm - 如何判断给定运行时作为 'n' 函数的算法的相对效率？

Question

考虑两种算法，A 和 B。这些算法都解决相同的问题，并且具有时间复杂度(根据他们执行的基本操作的数量)给定分别由

a) (n) = 9n+6

b) (n) = 2(n^2)+1

(i) 哪种算法渐近最好？

(ii) 对于小的输入大小 n 哪个是最好的，对于 n 的值是什么案件？ (您可以在必要时假设 n>0。)

我认为是 A，对吗？

B 部分的答案是什么？他们到底想要什么？

Answer 1

Which algorithm is the best asymptotically?

要回答这个问题，您只需要看一下两个函数中 n 的指数:渐近地，n² 将比 n 增长得更快。所以 A ∈ O(n) 渐近地是比 B ∈ O(n²) 更好的选择。

Which is the best for small input sizes n, and for what values of n is this the case? (You may assume where necessary that n>0.)

要回答这个问题，您需要找到两个函数具有相同值的交点。对于 n=5，两个函数的计算结果都是 51(参见 9n+6=2(n^2)+1 on Wolfram Alpha)。由于 A(4)=42 和 B(4)=33，对于 n < 5，B 是更好的选择。