因为我正在攻读GRE,所以我正在寻找这个问题的解释:
对于50号条目,算法在10秒内运行。如果算法是二次方的,如果输入的大小为100,它会在几秒钟内花费多少时间在同一台计算机上?
我看不出时间和输入之间的关系。
考虑:O(n^2) -> O(50^2) =! 10 (seconds)
此外,我想更多地了解这个主题,所以如果可以,请添加任何来源。
谢谢。
请注意,术语很草率,时间复杂度没有时间概念(是的,名称是欺骗)。
由于我们在big-O框架下工作,忽略小于O(n2)的项,二次函数可表示为
t = c * n2
给定(t,n)对具有值(10,50),我们有
10 = c * 2500 c = 1/250 = 4/1000
求得(t,100)得到
t = 4/1000 * 10000 = 40
有一种更快,更有洞察力的方法来解决这个问题。 受过训练的眼睛可以立即将答案发现为40。
考虑这个功能电源功能:
t = c * nk
现在让我们考虑输入m0和m1,其中m1 = a * m0是m0的(整数)倍数。 让我们比较各自的t0,t1:
t0 = c *(m0)k t1 = c *(m1)k = c * ak *(m0)k
因此,我们看到对于多项式时间函数t1 / t0 = ak,或t1 = ak * t0。
两个输出之间的比率是它们的输入与第k个功率之间的比率。
对于二次函数k = 2,因此两个输出之间的比率是两个输入之间的比率的平方。 如果输入加倍(比率= 2),则输出翻两番(比率= 22 = 4)。 如果输入三倍(比率= 3),则输出为九倍(比率= 32 = 9)。
一个好的助记符技巧是要记住输入比率与输出比率的函数与给定函数的类型相同。 我们给出了二次函数,这是输入和输出比率之间的关系:
input output
ratio ratio
1 1
2 4
3 9
4 16
5 25
... ...
问题告诉您输出加倍(从50到100个条目),因此输出必须翻两番(从10到40),因为函数是二次的。 正如您所看到的,问题的所有数据都是优雅地使用,没有任何核心计算。
建议外部消息来源不赞成,但在这种情况下,我不得不推荐阅读:
看看你是否可以回答这些问题:
Big-O不会告诉您条目大小和执行时间之间的确切相关性,而是告诉您条目大小增长与执行时间增长之间的近似相关性。所以:O(n)
复杂性意味着条目大小和执行时间成正比(如果输入是3倍大,那么执行时间也将是3倍),O(n^2)
意味着如果条目大小是3倍大,然后执行时间将延长9倍等。
在您的情况下,50号条目的初始执行时间是10秒。如果输入变为100大小的条目,那么通过简单划分,我们可以判断它的100 / 50 = 2
倍大。知道算法的Big-O是O(n^2)
,我们可以告诉执行时间将是2^2 = 4
倍。因此,如果初始执行时间是10秒,那么较大输入的执行时间将近似为10 seconds * 4 = 40 seconds
。
相关的问题:Rough estimate of running time from Big O
关于big-o的好文章:https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/