algorithm - 大 O 和时间复杂度

Question

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

是不是就这么简单...

M=5分钟 4M=20分钟

?

Answer 1

由于 Big O 只是一个近似值，您无法计算实时时间，但是您可以进行一些估计。在你的情况下是

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

注意:我使用符号 ~ 来表示近似值。

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

M 大约需要 M^2 时间

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