算法的时间复杂度

Question

大小为n = 100的算法需要21秒才能运行.大小n = 1000需要31秒,而n = 10000需要41秒才能运行.运行的复杂性是什么？

如果我尝试O(n)然后:T(n)=(21*1000)/ 100 = 210 s(非O(n))
如果我尝试O(n ^ 2)那么:T(n)=(21*1000 ^ 2)/ 100 ^ 2 = 2100 s(非O(n ^ 2))
如果我尝试O(log n)则:T(n)=(21*log1000)/log100=31.5(不是O(log ^) ))

我给出的另一个选择是O(1/n).我该如何计算？

Answer 1

看起来像一个O(lgn).

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