9硬幣平衡難題的算法複雜性？

Question

問題：你有3^x硬幣，其中一個比其他人重。你必須使用一套平衡秤來確定是哪個硬幣。問題在於你只能使用秤來稱量x。

例如，

[0, 0, 1, 0, 0, 0, 0, 0, 0] 
    ^

Heavier coin is at index 2. 

作爲一種編程挑戰，這並不是特別有效，因爲你可以遍歷數組尋找1，即。上）。正確答案是將硬幣分成三組，然後稱重前兩組。這使您可以確定三個組中的哪一個包含硬幣。遞歸地稱即組等等，直到你剩下只有一個硬幣。 （稱量可以通過獲取子列表的總和來模擬）。

我一直在想弄清楚這個算法的複雜性是什麼。起初，我認爲它是O（log n），因爲你排除了數據集的一部分來收斂答案，有點像二分查找。但是你必須遍歷每個組來確定它的重量，這將是O（n）。

Here is a reasonable example of the algorithm in C++。請注意，我的C++充其量是最差的，因此嘗試着重於邏輯而不是代碼本身。經過手工操作（有9和27個硬幣），我覺得它實際上是一個O（n）算法。我應該如何通過數學來確定？我還沒有做過證明。

Answer 1

它是N * log（N）。 log（N）是迭代次數，N是每次迭代的子集總和。