Агуулгыг алгасах

$K$-р эрэмбийн статистик $O(N)$-д

$N$ хэмжээтэй $A$ массив ба $K$ тоо өгөгдсөн. Бодлого нь массив дахь $K$-р хамгийн их тоо буюу $K$-р эрэмбийн статистикийг олоход оршино.

Үндсэн санаа нь хурдан эрэмбэлэлтийн (quick sort) алгоритмын санааг ашиглах явдал юм. Үнэндээ алгоритм нь энгийн боловч хурдан эрэмбэлэлтээс ялгаатай нь дунджаар $O(N)$-д ажилладгийг батлах нь илүү хэцүү.

Implementation (not recursive)

template <class T>
T order_statistics (std::vector<T> a, unsigned n, unsigned k)
{
    using std::swap;
    for (unsigned l=1, r=n; ; )
    {
        if (r <= l+1)
        {
            // the current part size is either 1 or 2, so it is easy to find the answer
            if (r == l+1 && a[r] < a[l])
                swap (a[l], a[r]);
            return a[k];
        }

        // ordering a[l], a[l+1], a[r]
        unsigned mid = (l + r) >> 1;
        swap (a[mid], a[l+1]);
        if (a[l] > a[r])
            swap (a[l], a[r]);
        if (a[l+1] > a[r])
            swap (a[l+1], a[r]);
        if (a[l] > a[l+1])
            swap (a[l], a[l+1]);

        // performing division
        // barrier is a[l + 1], i.e. median among a[l], a[l + 1], a[r]
        unsigned
            i = l+1,
            j = r;
        const T
            cur = a[l+1];
        for (;;)
        {
            while (a[++i] < cur) ;
            while (a[--j] > cur) ;
            if (i > j)
                break;
            swap (a[i], a[j]);
        }

        // inserting the barrier
        a[l+1] = a[j];
        a[j] = cur;

        // we continue to work in that part, which must contain the required element
        if (j >= k)
            r = j-1;
        if (j <= k)
            l = i;
    }
}

Тэмдэглэл

  • Дээрх санамсаргүй алгоритмыг quickselect гэж нэрлэдэг. Зөв ажиллуулахын тулд дуудахаасаа өмнө $A$-г санамсаргүйгээр холих буюу санамсаргүй элементийг заагаар ашиглах хэрэгтэй. Мөн тодорхойлсон бодлогыг шугаман хугацаанд бодох детерминистик алгоритмууд бий, жишээ нь медианы медиан.
  • std::nth_element нь үүнийг C++-д боддог боловч gcc-ийн хэрэгжүүлэлт хамгийн муу тохиолдолд $O(n \log n )$ хугацаанд ажилладаг.
  • $K$ хамгийн бага элементийг олох нь $K$-р элементийг олоход шугаман нэмэлт зардлаар шилжинэ, учир нь тэдгээр нь яг $K$-рээс бага элементүүд юм.

Дасгал бодлогууд