一个算法对于大小为100的输入花费0.5ms。求1min能解决多大规模的问题?a.是线性的答案:12000timesaslargeaproblem,orinputsize1,200,000b.N(logN)答案:inputsizeofapproximately425,000c.N^2

Question

一个算法对于大小为100的输入花费0.5ms。求1min能解决多大规模的问题?
a.是线性的 答案: 12000 times as large a problem, or input size 1,200,000
b.N(logN) 答案: input size of approximately 425,000
c.N^2 答案: √12000 times as large a problem, or input size 10,954
d.N^3 答案: 120001/3 times as large a problem, or input size 2,289
我的解法是求出这个比例系数K, 然后带入时间求解, K*复杂度=T.
a是线性的, 也就是 100K= 0.5*10^-3 , 然后K=0.5*10^-3/100 , 解0.5*10^-3/100N=60, 解得: 1.2*10^7, 错误
b: 完全不会解这个式子
c: 相同的解法, 100^2K=0.5*10^-3 , K=0.5*10^-7 , 解得N=sqrt(12*10^8) , 这和结果的10954差的太多了!
我不知道我的解法哪里有问题, 复杂度越高, 差的数字就越大. 到底是哪里出了问题了?拜托了!

Answer 1

你的没有错误，所有的错误是写答案的家伙把60S和0.5ms的倍数算错了，他算成12000，少了一个0，不过他的算法比你精简。 K根本是不必要的。