0

我试图了解 n^2 如何在 n < 100 时比 nlogn 快，而在 n >= 100 时则相反。通常情况并非如此，但这是一个我不想回答但引导我去做的练习正确的方向。我可以在图中描绘两个函数，n = 100 处的交集，因为 n < 100 O(n^2) 更快，而 n > 100 O(nlogn) 更快。

我想出了 an^2+b 和 c*nlog(n)+d

我在这里理解的关键是不断产生差异。但难的是我需要想出满足上述情况的常量。有没有一种方法或技术已经完成，或者我是否正确地走错了方向？

原始问题：James 和 Brad 正在争论他们的排序算法的性能。James 声称他的 O(N logN) 时间算法总是比 Brad 的 O(N2) 时间算法快。为了解决这个问题，他们在许多随机生成的数据集上实现并运行这两种算法。令 James 沮丧的是，他们发现如果 N < 100，O(N2) 时间算法实际上运行得更快，并且只有当 N >= 100 时，O(N logN) 时间算法才会更好。解释为什么上述情况是可能的。你可以给出数值例子。

4

3 回答 3

1

取你已有的公式，an^2+b 和 c*nlog(n)+d

将 n 替换为 100，并将它们设置为相等。这将向您展示 a、b、c 和 d 之间的关系。选择一组符合该约束的值。

于 2013-09-12T03:03:32.440 回答
1

试着思考每个方程中的每个变量的含义。我会继续忽略某些变量（根据需要将它们设置为 0 或 1）并专注于决定性变量留下的含义。每个 A、B、C 和 D 的含义是什么？这些变量的界限是什么？例如，负运行时不是一个东西，所以没有变量可以是负的。听起来很明显，但问题是方向，而不是实质。为了获得额外的好处，请尝试使 A = C = 1 并操纵 B 和 D。

于 2013-09-12T03:25:09.640 回答
0

下面的链接在图中显示了两个函数确实相交的清晰案例。我相信它可以通过一个具体的例子帮助你理解。

http://mohalgorithmsorbit.blogspot.com/2013/12/complexity-theory-approaching.html

于 2014-03-01T15:54:46.203 回答