算法

我希望@greybeard做出了关键的观察in their answer：
无论如何，如果您将每个元素与当前第二大值进行比较，我预计与最大值进行比较的可能性会越来越小。
原因是如果输入是随机的，则：

• 前半部分的最大值可能是后半部分中最大的值。
• 上半部分的第二大值也是如此。

在极端情况下，假设最大的两个值是您开始的前两个值：

• 比较最大的第一个，如果值低于第一个，第二个最大的第二个将 * 总是 * 导致2次比较。
• 比较第二个最大的第一个，如果值大于第二个，则最大的第二个将 * 总是 * 导致单个比较。

当然，你不会立即知道最大的或第二大的。平均而言，在查看了50%的元素之后，您就会知道它们，因此，您将在前半部分对每个元素进行2次比较，在后半部分对每个元素进行1次比较，总共进行1.5N次比较。

生 rust

我们应该有一个签名的形式：

fn max_pairwise_product(values: &[i64]) -> Option<i64>;

首先，如果values为空，则不会有任何类型的乘积。
其次，注意使用&[i64]作为参数，而不是&Vec<i64>：它更通用。你可以从一个Vec<T>，一个VecDeque<T>，一个[T; N]得到一个&[T]，...

命令

让我们先写命令式代码（Playground link）：

fn max_pairwise_product(values: &[i64]) -> Option<i64> {
    //  `[T]::get` returns an `Option<&T>`.
    //  `Option<&T>::copied` returns an `Option<T>`, if `T` is `Copy.
    //  `?` short-circuits the operation when things don't work out.
    let first = values.get(0).copied()?;
    let second = values.get(1).copied()?;

    //  Can be expressed as `(first.max(second), first.min(second))` too.
    let (mut first, mut second) = if first > second {
        (first, second)
    } else {
        (second, first)
    };

    //  And from then, we scan the rest of the values using sub-slicing to
    //  express that we want to skip the first 2 values.
    //  The `&` in front of `v` is pattern-matching to make `v` a value,
    //  instead of a reference.
    for &v in &values[2..] {
        if v <= second {
            continue;
        }

        if v <= first {
            second = v;
            continue;
        }

        second = first;
        first = v;
    }

    Some(first * second)
}

功能

不过，Rust确实有更多的技巧，特别是模式匹配（更多）和用Iterator方法替换循环可以产生非常好的代码。
同样的算法实际上可以表示为（Playground link）：

fn max_pairwise_product(values: &[i64]) -> Option<i64> {
    //  The all-powerful `let .. else` form of pattern-matching, the "my way
    //  or the highway" style of matching for quickly getting out of here.
    let [first, second, tail @ ..] = values else { return None };

    let (first, second) = (first.max(second), first.min(second));

    let (first, second) = tail
        .iter()
        .copied()
        .fold((*first, *second), |(first, second), v| {
            if v <= second {
                (first, second)
            } else if v <= first {
                (first, v)
            } else {
                (v, first)
            }
        });

    Some(first * second)
}

这是在切片上使用模式匹配来以可视化的方式提取元素（尽管tail @ ..部分目前只在夜间使用），以及强大的fold算法。

我不知道你的算法有什么用。只使用两个变量并且只迭代一次似乎更有效率。

fn max_pairwise_product(a: &Vec<i64>) -> i64 {
    // assign to first values
    let (mut largest, mut second_largest) = (i64::MIN, i64::MIN);

    // only one iteration
    for &i in a.iter() {
        if i > largest {
            // i is larger than both, so shift the positions
            (largest, second_largest) = (i, largest);
        } else if i > second_largest {
            // i is only larger than the second largest, so change that
            second_largest = i;
        }
    }
    largest * second_largest
}

我不知道如何在 * 预期 * 比较次数为1.5n 的情况下 * 获得第二大 *（或 * 两个最大 ），或优于2n最坏情况 *。

• 第二大 * 有两种解释：

在0, 1, 2, 2中，* 最大的两个 * 是2, 2，但我在这里称1 * 第二大 *。
无论如何，如果你将每个元素与当前的 * 第二大 * 进行比较，我预计与最大值的比较将变得越来越不可能。
对于“均匀随机输入”，我期望n+n比较，k甚至不是1/2。
关于找到最大的产品有很多问题，很少有比较和答案。

你几乎有了，你的担心是正确的。它们可以在逻辑上消除。
首先，您可以简单地检查最后一个元素的长度是否为奇数。这是最坏情况下的两个比较。
第二，可以跟踪max元素的索引。
我把你的算法换了一下，让它更简单。我使用原始切片进行存储，使前半部分为较大的数字，后半部分为较小的数字。然后，我在前半部分运行朴素算法。这给了我两个数字和指数。然后，我检查与max的索引对应的索引处的较小的一半，因为这是较小的一半中唯一可能大于第二个max的数字。
最后，检查最后一个元素的长度是否为奇数。
这个算法在第一阶段进行N/2次比较，就像你的算法一样。第二阶段在列表的一半上使用2N算法。然后有三个额外的比较。总的来说，这是N/2 + 2N/2 + 3或0（1.5N）。

fn reordering_(a: &mut [i64]) -> i64 {
    let mid = a.len() / 2;
    let (half1, half2) = a.split_at_mut(mid);

    // Put max items in the first half
    for (x, y) in half1.iter_mut().zip(half2) {
        if y > x {
            std::mem::swap(x, y);
        }
    }

    // Find two largest in first half
    let mut largest = [(i64::MIN, 0), (i64::MIN, 0)];
    for (index, &i) in a[..mid].iter().enumerate() {
        if i > largest[1].0 {
            if i > largest[0].0 {
                largest = [(i, index), largest[0]]
            } else {
                largest[1] = (i, index);
            }
        }
    }

    let matching = largest[0].1 + mid;
    let mut largest = largest.map(|(n, _)| n);

    if a[matching] > largest[1] {
        largest[1] = a[matching];
    }

    if a.len() % 2 == 1 {
        let &last = a.last().unwrap();
        if last > largest[1] {
            if last > largest[0] {
                largest.reverse();
                largest[0] = last;
            } else {
                largest[1] = last;
            }
        }
    }

    largest[0] * largest[1]
}

你可以做比1.5n更好的比较。
要理解的关键点是这样的：为了确定最大的元素，您必须在某个时候将其与第二大元素进行比较。
您可以使用此方法仅在n + ceil（log 2 n）- 2次比较中获得最大值和第二大值。
首先，为了找到最大的元素，将元素分成对，比较每对中的元素，并选择所有ceil（n/2）个获胜者。对获胜者重复此过程，直到只剩下最大的元素。这就像是淘汰赛
这个寻找最大元素的过程需要ceil（log 2n）轮，并且一起进行n-1次比较。在每一轮中，最大的元素与它配对的元素进行最多一次比较。收集这些配对并使用ceil（log 2n）-1比较来找到其中最大的。这将是第二大因素。