algorithm - 贪心算法的正确性

Question

In non-decreasing sequence of (positive) integers two elements can be removed when . How many pairs can be removed at most from this sequence?

于是想到了以下解决方案:

• 我将给定的序列分成两部分(第一部分和第二部分)。
• 分别为它们分配迭代器 - it_first := 0 和 it_second := 0。计数 := 0
• 当 it_second != second.length
  • 如果 2 * 第一个 [it_first] <= 第二个 [it_second]
    • count++, it_first++, it_second++
  • 其他
    • it_second++
• 计数就是答案

例子:

计数 := 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 --> 错误，it_second++

4. 8 ?<24 --> true，计数++it_second 到达最后一个元素 - END。

5. 计数 == 3

线性复杂度(最坏的情况是没有要移除的元素。n/2个元素与n/2个元素比较)。所以我缺少的部分是算法的“正确性”——我读过关于贪婪算法的证明——但主要是树，我找不到类比。任何帮助，将不胜感激。谢谢!

编辑:我所说的正确性是指: * 有用 * 它不能更快​​地完成(在 logn 或常量中)

我想放一些图片，但由于声望点 < 10 - 我不能。(我的意思是一开始就使用一种 latex ;))

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. 当我们拥有这个属性时，我们可以简单地用数组中的最小元素替换所有对的所有 first all 元素中的最小元素，所有 first 元素中第二小的元素替换为数组中的第二小元素数组等而不会使任何对无效。

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

   • 关于数组长度为奇数的情况的注意事项:中间元素的位置无关紧要:到前半部分还是后半部分。前半段没用(后半段元素不够)。如果我们把它放到后半部分，它是无用的两个(假设我们拿走了它。这意味着后半部分的某个地方有“自由空间”。因此，我们可以将一些元素移动一个并摆脱它).

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