數量同時最大和最小元素

Question

這種比較的是，我試圖解決的問題：

---

下面的分而治之算法尋找同時最大值和最小值：

• 如果有一個項目，它是最大和最小

• 如果有兩個項目，然後對它們進行比較，並在一個比較，你可以找到日最大值和最小值。否則，將輸入分成兩半，儘可能均勻地分開（如果N是奇數，則兩半中的一個將具有比另一半多一個元素）。

• 遞歸地找到每一半的最大值和最小值，然後在兩個額外的比較中產生整個問題的最大值和最小值。

（b）假設N的形式爲3 + 2k。這個算法使用的確切比較次數是多少？

---

對於這一點（二），我試圖找到一個遞推方程來解決，但它沒有奏效。 我試過

T(n)= T(n/2+1) + T(n/2) + 3 

，其中三是成本最低，當我嘗試3個輸入。 有幫助嗎？

Answer 1

您的遞推方程不應該有n的特殊情況，任期= 3的算法爲您提供了這些事實：

• T（1）= 0
• T（2）= 1
• T（N）（N> 2）= T（地面（N/2））+ T（小區（N/2））+ 2

這應該是所有你需要制定出答案。