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

Question

考虑两种算法,A和B.这些算法都解决了同样的问题,并且具有时间复杂性(就其执行的基本操作的数量而言)分别给出

一个) (n) = 9n+6

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

(i)哪种算法最优化渐近？

(ii)对于小输入尺寸n,哪种是最佳的,对于这种情况,n的值是多少？(您可以在必要时假设n> 0.)

我认为这是A.我是对的吗？

B部分的答案是什么？他们究竟想要什么？

Answer 1

哪种算法渐近最好？

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

这是最适合小输入大小不一ñ,和什么样的价值观的ñ是这种情况？(您可以在必要时假设n > 0.)

要回答这个问题,您需要找到两个函数具有相同值的交点.并且对于n = 5,两个函数都评估为51(见Wolfram Alpha上的9n + 6 = 2(n ^ 2)+1).由于A(4)= 42且B(4)= 33,因此B是n <5 的更好选择.

Answer 2

我认为绘制这些函数对于了解正在发生的事情非常有帮助.

Answer 3

您可能应该首先熟悉渐近学、大 O 表示法等。渐进地，a 会更好。为什么？因为可以证明，对于足够大的N，a(n) < b(n) 对于n> N。

证明留给读者作为练习。