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

  • AndyMcMillinTV

    AndyMcMillin

    6 HAZİRAN 2007
  • AyfionGaming

    AyfionGaming

    20 ŞUBAT 2013
  • Photoshop Training Channel

    Photoshop Tr

    13 Temmuz 2012