一个算法对于大小为100的输入花费0.5ms。求1min能解决多大规模的问题?

一个算法对于大小为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差的太多了!
我不知道我的解法哪里有问题, 复杂度越高, 差的数字就越大. 到底是哪里出了问题了?拜托了!
痘痘儿 1年前 已收到1个回答 举报

hainansss 幼苗

共回答了14个问题采纳率:85.7% 举报

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

1年前 追问

5

痘痘儿 举报

那他是怎么算的呢? 我不知道xxxx times 是怎么算出来的, 是表示什么? 直译的话是xxxx次, xxxx次和input size yyyy 有什么区别, 怎么也想不通, 拜托了

举报 hainansss

times 的意思是“倍数”。 60秒是0.5毫秒的120000倍。他算成12000倍,所有的依据都是这样来的。
a 时间是120000倍,所以数量是120000*100
logN 是以10为底求对数。 log(100)=2 (意思是10的2次方=100).
经过计算 425,000*log425000约等于2400000 除以200 等于12000(他又少算了一个0)
c 12000开根号是109.54 乘以100 就是10954,而你是120000开根346.41,乘以100就是34641.这就是你们的差别。

痘痘儿 举报

哦哦, 明白了,非常感谢
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 18 q. 0.625 s. - webmaster@yulucn.com