Lun*_*nar 1 algorithm
我试图找到大理石问题的下界,问题是;
有n个大理石,可能有1个比其他大理石轻的大理石,或者它们可能都是相同的.
我从标准称重问题中得知,找到较轻的大理石的下限是O(log3 n).
但是在这种情况下可能是所有大理石都相等的情况,这会改变下限吗？
那么下限是否等于可以解决的最佳情况？
Agr*_*jag 5
这不会改变一般问题的下限.因为其中一个弹珠可能更轻,在这种情况下你需要O(log3 n)重量.
对于某些输入,您可以更快地完成它,并不会改变最快可能的通用算法(即适用于所有合法输入的算法)的事实,即O(log3 n)
这类似于基于比较的排序的下限为O(n*log2 n),尽管您可以在O(n)中检测已经排序的输入.
归档时间：
13 年，11 月 前
查看次数：
96 次
最近记录：