SORU
30 EKİM 2008, PERŞEMBE


Nasıl O n uzunluğu sıralanmamış bir dizi(n) hazırlanmasında en büyük elemanı bulmak için?

O n uzunluğu sıralanmamış bir dizi(n) hazırlanmasında en büyük elemanı bulmak için bir yol olduğuna inanıyorum. Ya da belki de "O(n) falan. olur böyle şeyler Bunu nasıl yapabiliriz?

CEVAP
30 EKİM 2008, PERŞEMBE


Bu bulgu denirk-inci mertebeden istatistik. Çok basit rastgele bir algoritma var (aradıquickselect) O(n) ortalama süre alarak, ve çok karmaşık olmayan rasgele algoritması O(n) en kötü durum alma zamanı. Wikipedia, biraz bilgi var ama çok iyi değil.

İhtiyacınız olan her şey these powerpoint slides. O(n) kötü durum algoritma: temel algoritma çıkartmak için

Select(A,n,i):
    Divide input into ⌈n/5⌉ groups of size 5.

    /* Partition on median-of-medians */
    medians = array of each group’s median.
    pivot = Select(medians, ⌈n/5⌉, ⌈n/10⌉)
    Left Array L and Right Array G = partition(A, pivot)

    /* Find ith element in L, pivot, or G */
    k = |L|   1
    If i = k, return pivot
    If i < k, return Select(L, k-1, i)
    If i > k, return Select(G, n-k, i-k)

Ayrıca çok güzel Cormen ve ark Algoritmalar kitabın Giriş bölümünde detaylı.

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • jocc talking shit

    jocc talking

    6 NİSAN 2007
  • Richard Laxa

    Richard Laxa

    30 AĞUSTOS 2012
  • SegaAmerica

    SegaAmerica

    5 Mart 2008