贪婪算法的正确性

Question

在(正)整数的非递减序列中,当可以去除两个元素时 .从这个序列中最多可以删除多少对？

所以我想到了以下解决方案:

• 我采用给定的顺序并分成两部分(第一和第二).
• 分别为它们分配迭代器 - it_first:= 0和it_second:= 0.count:= 0
• 当it_second!= second.length
  • if 2*first [it_first] <= second [it_second]
    • count ++,it_first ++,it_second ++
  • 其他
    • it_second ++
• 伯爵就是答案

例:

count:= 0

[1,5,8,10,12,13,15,24] - > 第一名:= [1,5,8,10],第二名:= [12,13,15,24]

1. 2*1？<12 - > true,count ++,it_first ++和it_second ++

2. 2*5？<13 - > true,count ++,it_first ++和it_second ++

3. 2*8？<15 - > false,it_second ++

4. 8？<24 - > true,count ++ it_second到达最后一个元素 - END.

5. count == 3

线性复杂度(最坏的情况是没有这样的元素被删除.n/2个元素与n/2个元素相比).所以我缺少的部分是算法的"正确性" - 我已经阅读了贪婪算法证明 - 但主要是树木,我找不到类比.任何帮助,将不胜感激.谢谢!

编辑: 正确性我的意思是:*它的工作原理*它不能更快​​地完成(在logn或常量)

我想放一些图形,但由于声誉点<10 - 我不能. (我的意思是一开始就有一种乳胶;))

Answer 1

1. 正确性：

   • 我们假设可以删除的最大对数是k。主张：存在一个最优解，其中所有对的第一个元素是k数组的最小元素。证明：我将证明可以将任何解决方案转换为包含第一个k元素作为所有对的第一个元素的解决方案。

     1. 假设我们有两对(a, b)，(c, d)例如a <= b <= c <= d、2 * a <= b和2 * c <= d。在这种情况下，对(a, c)和(b, d)也是有效的。现在我们有了a <= c <= b <= d。因此，我们总是可以以这样的方式转换对，即任何对中的第一个元素不大于任何对中的第二个元素。

     2. 当我们拥有这个属性时，我们可以简单地将所有对的所有第一个所有元素中的最小元素替换为数组中的最小元素，所有第一个元素中的第二小的元素 - 替换为数组中的第二小的元素，依此类推，而不会失效任何一对。

   • 现在我们知道存在一个包含k最小元素的最优解。很明显，我们不能通过采用适合每个元素的最小未使用元素（使其变大只能减少下一个元素的答案）来使答案变得更糟。因此，这个解决方案是正确的。

   • 关于数组长度为奇数时的情况的注释：中间元素的位置并不重要：到前半部分还是后半部分。前半部分没用（后半部分没有足够的元素）。如果我们把它放到后半部分，那就没用了（假设我们拿走了它。这意味着后半部分的某个地方有“自由空间”。因此，我们可以将一些元素移一并摆脱它） ）。

2. 时间复杂度方面的最优性：该解决方案的时间复杂度为O(n)。在最坏的情况下，如果不读取整个输入，我们就无法找到答案，而读取已经是O(n)时候了。因此，该算法是最优的。