0

An algorith with size n=100 takes 21 seconds to run. With size n=1000 it takes 31 seconds and with n=10000 takes 41 seconds to run. What is the running complexity?

If I try O(n) Then: T(n)=(21*1000)/100 = 210 s (Not O(n))
If I try O(n^2) Then: T(n)=(21*1000^2)/100^2 = 2100 s (Not O(n^2))
If I try O(log n) then: T(n)=(21*log1000)/log100=31.5 (Not O(log n))

The other option I am given is O(1/n). How do I calculate this?

4

2 回答 2

6

看起来像一个O(lgn).

时间n是T(n) = 10*log(n) + 1日志的基数为 10 时。

于 2011-02-03T14:40:33.257 回答
1

为了解决这个问题，首先绘制来自各个类的一些函数。例如要了解O(n)线性类绘制函数T(n)=n和了解O(n^2)类绘制函数T(n)=n^2。这将帮助您识别各种功能的形状。

之后，用 x 轴上的 n 值和 y 轴上的定时值绘制问题中给出的点。您应该能够快速识别此问题中的形状。

提示：这不是O(log n) :-)

于 2011-02-03T14:51:19.807 回答