我试图了解 n^2 如何在 n < 100 时比 nlogn 快,而在 n >= 100 时相反。通常情况并非如此,但这是一个我不想回答的练习,而是引导我走向正确的方向。我可以在图中描绘两个函数,当 n < 100 O(n^2) 时,n = 100 处的交点更快,而当 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) 时间算法才更好。解释为什么上述情况是可能的。您可以给出数值示例。
最佳答案
取你已有的公式,an^2+b 和 c*nlog(n)+d
将 n 替换为 100,并使它们相等。这将显示 a、b、c 和 d 之间的关系。选择一组符合该约束的值。
关于algorithm - 练习(大哦): How do find intersection of two functions where n = 100 for example,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18754554/