找到最強的人算法

-2

我想知道如何解決以下問題比我想出的更好。基本上你有n個人，你想找出那些n個人中最強壯的人，讓他們掰手腕。我想通過n-1決鬥如何解決這個問題，但是有沒有其他解決方案，如log（n）og 3n/2？找到最強的人算法

謝謝。

來源

2017-09-06 briyan

我認爲每個人都必須進行n-1場決鬥，因爲總共有n人會有n *（n-1）場決鬥。 – zenwraight

，因爲畢竟這些決鬥只有你會有每個人的得分和實力，然後你可以把他們排序，以獲得最強大的人 – zenwraight

@harold我想它應該是傳遞，否則每個人必須執行n-1決鬥 – zenwraight

如果我們假設強度爲weakly-ordered，那麼對於某些A，B，C，假設「如果A比B強，B比C強，C永遠不會比A強」。是，我們可以假設，如果「A比B強」，「B比C強」，那麼「A比C強」。

因此，我們的弱排序比賽將包括每個鄰居比較自己與鄰居。這在一輪內（N/2比較）消除了半場參賽者。我們重複強度的這種測試，直到只有一個人仍然是：

O O O O O O 
    \/ \/ \/
    O  O  O 
     \ /  | 
     \/  | 
     O   O 
      \  /
      \ /
      \ /
       O

的時間這種算法的複雜度爲O（N）和「發」的數量是地板（log_2（N））。在我的例子中，N = 6，floor（log_2（6））= 2。它是O（N），因爲我們遇到了N/2，N/4，N/8形式的多個面。 ... 1，給我們留下總和N/2 + N/4 + N/8 + ... + 1，或者從0到floor（log_2（N ）），並且由於我們知道floor（log_2（N））小於無窮大，所以我們可以安全地說結果小於或等於summation of the common geometric series乘以N，即爲N.因此O（N）

如果我們不能假設弱排序，那麼我們最終的結果是A可能擊敗B，B可能擊敗C，但C可以擊敗A.沒有辦法按照最強的順序「排序」這樣的集合最弱的，所以我們不得不讓每個人都對付每個人，以便我們可以計算一個勝利/損失記錄。然後我們可以通過他們的勝利來訂購我們的競爭對手這樣的算法來計算「全對」是O（N ）（由於比較的次數是Triangular Numbers減去N）：

1面對反對2，3，4（3 faceoffs）
2面對反對3和4（2 faceoffs，2已經面對反對1）
3面對反對4（1面脫落，已經面對反對1和2）

因此，我們有（n-1）+（n-2）+ ... + 1的面對面的總和等於0,

來源

2017-09-06 20:22:46 AndyG

downvoter可以解釋？ – AndyG

假設關係'更強'是過渡性的......每一場決鬥都會從一個考慮中刪除一個人。因此，你不能找到對手少於n-1的最強者。

來源

2017-09-06 19:34:59 DAle

現在他從來沒有提到每場對決都會被淘汰，現在如果A贏得對手B和B對C的勝利，那麼理解它似乎A應該贏得對C的勝利，但是如果C贏得了A的勝利呢？ – zenwraight

好吧，它似乎是傳遞，那麼你的情況是正確的@DAle – zenwraight

找到最強的人算法

回答

相關問題