复杂性类

Question

假设方法m1和m2是静态的无效的，并通过处理Object []类型的参数来计算相同的结果。经验上我们发现m1→T（N）= 100N和m2→T（N）= 10Nlog2N，其中时间以微秒为单位。对于什么尺寸的输入，最好使用m1和m2？ 所以我会用大数字m1，而我会用小数字m2？只是检查答案。

Answer 1

您正在寻找N > 0的值，因此100N > 10N log2 N，所以这只是一个代数问题。将双方除以10N，即得到10 > log2 N，即N < 2**10，即N < 1024。并不难 - ！）

Answer 2

嗯，登录 N的会打10的时候，N是1024，所以要根据您提供给我们的公式，你会用N <= 1024第二个和第一个为N >= 1024。 （你在边界上做什么并不重要 - 它们将是平等的。）

但是，从实际的角度来看，你应该很可能选择一个并保持那一个。你是否期望非常大的输入或许多小输入？这绝对是你的代码中的瓶颈？哪一种更简单的算法？

还有很多事情要决定哪个算法是最好的而不仅仅是给定输入中哪个算法最快。我宁愿保持一个简单的算法，它运行的速度比一个快速但却非常复杂的算法慢。

Answer 3

看看这个：http://www.wolframalpha.com/input/?i=plot+100*n+and+plot+10*n*log2(n)

我还没有想出如何修改，虽然规模。无论如何，以备将来参考。