计算算法的下限？

Question

我试图找到一个大理石问题的下界，问题是;

有n个弹珠，可能有1个大理石比其他的要轻，或者它们可能都是相等的。

我从标准称重问题中知道，找到较轻的大理石的下界是O（log3 n）。

但是在这种情况下，所有弹珠都是相等的情况下，这会改变下限吗？

那么下限是否等于它可以解决的最好情况？

Answer 1

这不会改变一般问题的下界。由于大理石之一可能更轻，并且在这种情况下，你将需要O（log3中N）称量。

对于某些输入，您可以更快地做到这一点，并不会改变最快可能的通用算法（即适用于所有合法输入的算法）的事实是O（log3 n）

尽管这是一个事实，你可以在O（n）的检测已分选的输入模拟到下界基于比较的排序是O（N * LOG2 N）。