估算算法從運行時間和變化率的增長順序

Question

我是一個初學者練習算法。下面的列表代表我運行的一個算法，記錄了變化的時間和比率。我不知道如何從這個列表中找出增長的順序。我必須考慮哪些因素？我非常感謝一個解釋性答案。

N |seconds | ratio | log(base of 2) ratio 
--------------------------------------- 
512 0.12 4.14  2.05 
1024 0.49 4.24  2.08 
2048 2.08 4.24  2.08 
4096 8.83 4.24  2.08 

Answer 1

比較爲您的最小輸入的時間的各種較大的輸入：

• 在N（512-> 1024）結果2倍的增加，在運行時間提高了4倍。
• N（512→2048）增加4倍會導致運行時間增加16倍。
• N增加8倍（512-> 4096）導致運行時間增加64倍。

由此，可以推斷的是在N，N- ķ X增加將導致在運行時間的ķ X增加，表明一個O（Ñ ）算法。