作者fonggo (锋哥)
看板TransCSI
标题[问题] 演算法的效率问题2
时间Fri Oct 10 01:15:34 2008
看起来好像很简单 但却不确定要怎麽写
An algorithm runs a given input of size n.
If n is 4096, the run time is 512 milliseconds.
If n is 16384, the run time is 8192 miilseconds.
What is the efficiency? What is the big-O notation?
我是这样算的:
n1=4096 f(n1)=512
n2=16384 f(n2)=8192
=> n2=4n1 f(n2)=16f(n1)
=> 因为n增为4倍时f(n)增为16倍
=> 16/4 = 4 ? 还是 16 = 4的平方?
=> 所以效率为 n四次方还是平方? 而big-O为 O(n四次方)还是O(n平方)?
请大家帮忙看一下 谢谢!
最後突然又想到一个问题:
效率是不是总是等於big-O呢?쀊
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.62.78.171
1F：推 avogau:O(n^2) 10/11 13:18