javascript - 中央値空間の複雑さの中央値

Question

Medians of Medians を使用して nth_number 選択アルゴリズムを実装しました。ウィキペディアでは、空間の複雑さは O( 1 ) であると述べています

これらの中央値の中から中央値を見つけるために、一時的な配列に中央値を格納する必要がありました。余分なメモリを使用せずにそれを行うにはどうすればよいでしょうか? スペースの複雑さを増加させるとは見なされない場合は、説明してください。

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;
            }
        }
    }
}