首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >用什么数学技术来比较算法的复杂性?

问用什么数学技术来比较算法的复杂性?
EN

Stack Overflow用户
提问于 2010-08-22 12:42:02
回答 4查看 3.6K关注 0票数 3

我今天开始阅读“算法入门”,但我对其中一个练习感到有点困惑。

练习1.2.2询问读者

假设我们在同一台机器上比较合并排序和插入排序的实现。对于大小为n的输入,插入排序在8n^2步骤中运行,而合并排序运行在64n日志n步骤中。 对于n的哪个值,插入排序优于合并排序?

我第一次尝试打开Wolfram并使用它绘制方程的图表,但我无法准确地比较这两张图。

然后,我尝试为n (200)选择一个随机值,在纸上计算方程,然后根据我的结果修改n的值。

但那花了太长时间。

解决这个问题的正确方法是什么?

EN

回答 4

Stack Overflow用户

发布于 2010-08-22 12:46:54

在两者相等的情况下,是否存在n的值?

在这点之上会发生什么?下面?

票数 6
EN

Stack Overflow用户

发布于 2012-01-31 18:22:57

对于n·43,8n2·64n日志n和插入排序优于合并排序,尽管合并排序在to (N log n)最坏情况下运行,插入排序在to(N2)最坏情况下运行,插入排序中的常量因素使小n的排序速度更快。因此,当子问题变得足够小时,在合并排序中使用插入排序是有意义的。考虑对合并排序的修改,其中大小为k或更小的子数组(对于某些k)不再被进一步分割,而是使用插入排序显式地排序。

票数 1
EN

Stack Overflow用户

发布于 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.

我希望它能帮助某人:)

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/3541512

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档