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

  • Dave Wallace

    Dave Wallace

    27 Kasım 2007
  • ICON

    ICON

    19 EKİM 2011
  • Jay Will

    Jay Will

    19 NİSAN 2006