大O和时间的复杂性

Question

假设已知算法为O(N ²)并且解决大小M的问题需要5分钟.关于解决4M大小问题需要多长时间？

它就像......一样简单

M = 5min 4M = 20min

？

Answer 1

由于Big O只是一个近似值,你不能计算实际时间,但肯定你可以有一些估计.在你的情况下,将

1 M ~ 5 min
4 M ~ 5 *(4*4) min ~ 80 min.

注:我用符号~来表示逼近.

O(N ^ 2)=>使用大小为N问题将需要大约N ^ 2时间

M将需要大约平方公尺时间

O(M)~ O(1M) 
=> 1^2*M^2 
=> M^2 
=> 5 min


O(4M) ~ (4M)^2 
=> 4^2*M^2 
=> 16*M^2 
=> 16*5 
=> 80 min