[問題] 演算法的效率問題2

[fonggo (鋒哥)]

看起來好像很簡單  但卻不確定要怎麼寫

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
推 avogau:O(n^2)