我今天开始阅读“算法入门”,但我对其中一个练习感到有点困惑。
练习1.2.2询问读者
假设我们在同一台机器上比较合并排序和插入排序的实现。对于大小为n的输入,插入排序在8n^2步骤中运行,而合并排序运行在64n日志n步骤中。 对于n的哪个值,插入排序优于合并排序?
我第一次尝试打开Wolfram并使用它绘制方程的图表,但我无法准确地比较这两张图。
然后,我尝试为n (200)选择一个随机值,在纸上计算方程,然后根据我的结果修改n的值。
但那花了太长时间。
解决这个问题的正确方法是什么?
发布于 2010-08-22 12:46:54
在两者相等的情况下,是否存在n的值?
在这点之上会发生什么?下面?
发布于 2012-01-31 18:22:57
对于n·43,8n2·64n日志n和插入排序优于合并排序,尽管合并排序在to (N log n)最坏情况下运行,插入排序在to(N2)最坏情况下运行,插入排序中的常量因素使小n的排序速度更快。因此,当子问题变得足够小时,在合并排序中使用插入排序是有意义的。考虑对合并排序的修改,其中大小为k或更小的子数组(对于某些k)不再被进一步分割,而是使用插入排序显式地排序。
发布于 2015-04-05 18:21:03
求解方程8n² < 64n lg n,得到方程2^(n/8) - n < 0。
一旦我不在测试中,只是做一些练习,我就用一个工具来查看f(n) = 2^(n/8) - n的图表。
正如这里所问的,插入排序与合并排序没有自然数量的n,对于f(n) < 0,我们得到:
2 <= n <= 43.
我希望它能帮助某人:)
https://stackoverflow.com/questions/3541512
复制相似问题