算法 - 查找数组的最佳元素

Question

我有一组相互不同的元素(x_1,x_2,...,x_n).每个元素都有一个正值(w_1,w_2,...,w_n).这些正值的总和为1.

我必须找到一个Optimal元素(x_k),它是:

和

我发现这个算法:

proc OptimalElement(arr[])
 prevs_w := 0
 nexts_w := 0

 for (i = 0; i <= n; i++)
 {
   wi := arr[i].w

   nexts_w := 1 - prevs_w - wi

   IF (prevs_w < 0,5 && nexts_w <= 0,5) THEN
     return arr[i]
   ELSE
     prevs_w := prevs_w + wi
   ENDIF
 }
end

但是该算法仅比较索引为i <k且i> k的项的总和.但我需要算法来计算x_i <x_k和x_i> x_k的项目总和.

算法应该有O(n)时间.你知道怎么解决吗？Thx提示.

输入示例:

x_i | 1; 4; 2; 3; 5
w_i | 0,1; 0,2; 0,3; 0,2; 0,2

Answer 1

您可以使用快速选择：

\n\n

\n
1. 选择一个枢轴（随机是一个好主意）
\n
2. 根据x坐标围绕该枢轴对数组进行分区，跟踪放置在其左侧的项的总和
\n
3. 如果s \xe2\x89\xa5 1/2，则递归到左侧。否则，递归到右侧
\n

\n\n

这里的问题是在最坏的情况下运行时间是O(n\xc2\xb2) 。然而，平均为O(n)（假设元素分布有些均匀）。还有其他具有确定性线性时间的基于分区的选择算法，您可能可以以类似的方式进行调整，但它们更复杂。

\n