[問題] 演算法的效率問題2
看起來好像很簡單 但卻不確定要怎麼寫
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
推
10/11 13:18, , 1F
10/11 13:18, 1F