中位空间复杂度中位数 [英] Median of Medians space complexity

问题描述

我使用中位数中位数实现了nth_number选择算法。
在维基百科上，它表示空间复杂度为O（1）

I implemented an nth_number selection algorithm using Medians of Medians. On wikipedia, it states that it's space complexity is O(1)

我必须将中位数存储在临时数组中，以便在这些中位数中找到中位数。您将如何在不使用任何额外内存的情况下做到这一点？如果不算增加空间复杂度，请解释。

I had to store the medians in a temporary array in order to find the median amongst those medians. How would you be able to do it without using any extra memory? If it does not count as increasing its space complexity, please explain.

function nth_number(v, n) {
    var start = 0;
    var end = v.length - 1;
    var targetIndex = n - 1;

    while(true) {

        var medians = []; /* Extra memory. */

        /* Divide our array into groups of 5s. Find a median within each */
        for(var i = start; i <= end; i += 6) {
            if(i + 5 < end)
                medians.push(findMedian(v, i, i + 5));
            else 
                medians.push(findMedian(v, i, end));
        }

        var median = findMedian(medians, 0, medians.length - 1); /* Find the median of all medians */

        var index = partition(v, median, start, end);

        if(index === targetIndex) {
            console.log(median);
            return median;
        }
        else {
            if(index < targetIndex) {
                start = index + 1;
                targetIndex -= index;
            }
            else {
                end = index - 1;
            }
        }
    }
}

推荐答案

选择算法需要重新排列输入向量，因为它会进行一系列分区。因此，可以合理地假设可以重新排列输入向量以找到中位数。

The selection algorithm needs to rearrange the input vector, since it does a series of partitions. So it's reasonable to assume that it is possible to rearrange the input vector in order to find the median.

一种简单的可行策略是交错插入五个一组，而不是使它们连续。因此，如果向量具有 N == 5K 个元素，则五个一组为：

One simple possible strategy is to interleave the groups of five, instead of making them consecutive. So, if the vector has N == 5K elements, the groups of five are:

(0,   k,    2k,   3k,   4k)
(1,   k+1,  2k+1, 3k+1, 4k+1)
(2,   k+2,  2k+2, 3k+2, 4k+2)
...
(k-1, 2k-1, 3k-1, 4k-1, 5k-1)

然后，当找到五个一组的中位数时，将其与该组中的第一个元素交换，这意味着中位数向量将最终成为重新排列向量的前 k 个元素。

Then when you find the median of a group of five, you swap it with the first element in the group, which means that the vector of medians will end up being the first k elements of the rearranged vector.

这篇关于中位空间复杂度中位数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！