9 硬币平衡难题的算法复杂性？
Algorithmic complexity of the 9 coin balancing puzzle?
问题：您有 3^x 个硬币，其中一个比其他的重。您必须使用一组天平来确定是哪一枚硬币。问题是您只能 x 使用秤称重。
例如。
[0, 0, 1, 0, 0, 0, 0, 0, 0]
^
Heavier coin is at index 2.
作为编程挑战，这并不是特别有效，因为您可以遍历数组寻找 1，即。在）。正确答案是将硬币分成三组，并称量前两组。这使您可以确定三组中的哪一组包含硬币。递归权衡 that 组等等，直到你只剩下一枚硬币。 （可以通过取子列表的总和来模拟称重）。
我一直在努力弄清楚这个算法的复杂度。起初我以为它是 O(log n)，因为你排除了部分数据集以收敛于答案，有点像二进制搜索。但是你必须遍历每个组来确定它的权重，这将是 O(n).
Here is a reasonable example of the algorithm in C++。请注意，我的 C++ 充其量也很差，所以请尽量关注逻辑而不是代码本身。
亲手经历了几个场景（有 9 个和 27 个硬币），我觉得它实际上是一个 O(n) 算法。我应该如何在数学上确定这一点？我还没打样呢
是 N*log(N)。 log(N) 是迭代计数，N 是每次迭代的子集之和。
运行时间为 O(N)，其中 N 是硬币的数量。要了解原因，请注意算法的每个“阶段”都会进行线性工作量，将剩余硬币的前三分之一和后三分之一相互比较，然后对剩余的三分之一元素递归地重复此过程。这给出了递归关系
T(N) = T(N / 3) + O(N),
通过主定理求解为 O(N)。直观上，每个阶段完成的功呈几何衰减，因此总完成的功是初始阶段完成的功的常数倍数。
虽然确实有 O(log N) 个阶段并且每个阶段都做 O(N) 个工作，但 O(N log N) 的界限并不严格，因为每个阶段完成的工作衰减得如此之快。
问题：您有 3^x 个硬币，其中一个比其他的重。您必须使用一组天平来确定是哪一枚硬币。问题是您只能 x 使用秤称重。
例如。
[0, 0, 1, 0, 0, 0, 0, 0, 0]
^
Heavier coin is at index 2.
作为编程挑战，这并不是特别有效，因为您可以遍历数组寻找 1，即。在）。正确答案是将硬币分成三组，并称量前两组。这使您可以确定三组中的哪一组包含硬币。递归权衡 that 组等等，直到你只剩下一枚硬币。 （可以通过取子列表的总和来模拟称重）。
我一直在努力弄清楚这个算法的复杂度。起初我以为它是 O(log n)，因为你排除了部分数据集以收敛于答案，有点像二进制搜索。但是你必须遍历每个组来确定它的权重，这将是 O(n).
Here is a reasonable example of the algorithm in C++。请注意，我的 C++ 充其量也很差，所以请尽量关注逻辑而不是代码本身。
亲手经历了几个场景（有 9 个和 27 个硬币），我觉得它实际上是一个 O(n) 算法。我应该如何在数学上确定这一点？我还没打样呢
是 N*log(N)。 log(N) 是迭代计数，N 是每次迭代的子集之和。
运行时间为 O(N)，其中 N 是硬币的数量。要了解原因，请注意算法的每个“阶段”都会进行线性工作量，将剩余硬币的前三分之一和后三分之一相互比较，然后对剩余的三分之一元素递归地重复此过程。这给出了递归关系
T(N) = T(N / 3) + O(N),
通过主定理求解为 O(N)。直观上，每个阶段完成的功呈几何衰减，因此总完成的功是初始阶段完成的功的常数倍数。
虽然确实有 O(log N) 个阶段并且每个阶段都做 O(N) 个工作，但 O(N log N) 的界限并不严格，因为每个阶段完成的工作衰减得如此之快。