algorithm - 算出算法的下限

下面是我正在学习的书的第4章中的伪代码。
我已经计算出如果有假币的话，它基本上能找到假币，因为它比普通硬币轻。

CW(A, i, j) /* n coins */
{
    if (i==j) return i /* base case */
    k := (j-i+1)/3
    Weigh A[i..i+k-1] and A[i+k..i+2k-1]
    if A[i..i+k-1] lighter
    CW(A, i, i+k-1);
    else if A[i+k..i+2k-1] lighter
    CW(A, i+k, i+2k-1);
    else /* equal */
    CW(A, i+2k, j);
}

现在我有两个问题。
我如何显示出要找到伪币所需的重量的数量的下限，或者确定是否存在？
有没有一个更好的算法来找到假币使用尽可能少的重量？

最佳答案

虽然你没有具体说明实际的问题是什么，但我假设你有n硬币，其中一个比其他硬币都轻，需要使用一个平衡秤来比较一组硬币。
要找到一个下限，请考虑这样一个事实：每一次称重只有3种可能的结果。因此k称重可以区分3k个不同的病例由于给定问题中存在n可能的情况（n假币的可能选择），您至少需要k=log3n称重才能找到它。
如果你分析给定的算法，你会发现这是它使用的权重，所以它是最优的。

关于algorithm - 算出算法的下限，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9559764/