Algoritme Favorit Saya: Menemukan Median dalam Waktu Linear (2018)

Menemukan median dalam O(n log n)

• Cara paling sederhana adalah mengurutkan daftar lalu memilih median
• Kompleksitas waktu sorting berbasis perbandingan adalah O(n log n)
• Contoh kode:

  def nlogn_median(l):  
      l = sorted(l)  
      if len(l) % 2 == 1:  
          return l[len(l) // 2]  
      else:  
          return 0.5 * (l[len(l) // 2 - 1] + l[len(l) // 2])  
  

Menemukan median dalam rata-rata O(n)

• Median bisa ditemukan dalam waktu linear rata-rata dengan menggunakan algoritme "quickselect"

• Algoritme rekursif yang dikembangkan oleh Tony Hoare

• Proses:

  1. Pilih indeks acak dari daftar dan tetapkan sebagai pivot
  2. Bagi daftar menjadi dua grup berdasarkan pivot:
     • elemen yang lebih kecil dari atau sama dengan pivot
     • elemen yang lebih besar dari pivot
  3. Telusuri secara rekursif grup yang berisi median

• Contoh kode:

  import random  
  
  def quickselect_median(l, pivot_fn=random.choice):  
      if len(l) % 2 == 1:  
          return quickselect(l, len(l) // 2, pivot_fn)  
      else:  
          return 0.5 * (quickselect(l, len(l) // 2 - 1, pivot_fn) + quickselect(l, len(l) // 2, pivot_fn))  
  
  def quickselect(l, k, pivot_fn):  
      if len(l) == 1:  
          assert k == 0  
          return l[0]  
  
      pivot = pivot_fn(l)  
      lows = [el for el in l if el < pivot]  
      highs = [el for el in l if el > pivot]  
      pivots = [el for el in l if el == pivot]  
  
      if k < len(lows):  
          return quickselect(lows, k, pivot_fn)  
      elif k < len(lows) + len(pivots):  
          return pivots[0]  
      else:  
          return quickselect(highs, k - len(lows) - len(pivots), pivot_fn)  
  

Bukti rata-rata O(n)

• Jika pivot membagi daftar kira-kira menjadi dua bagian, setiap pemanggilan rekursif bekerja pada setengah data dari langkah sebelumnya
• Bukti matematis:

  C = n + n/2 + n/4 + n/8 + ... = 2n = O(n)  
  

O(n) deterministik

• Menjamin waktu linear bahkan dalam kasus terburuk

• Memilih pivot dengan algoritme "median-of-medians"

• Proses:

  1. Bagi daftar menjadi grup berisi 5 elemen
  2. Urutkan setiap grup lalu pilih mediannya
  3. Pilih median dari para median sebagai pivot

• Contoh kode:

  def pick_pivot(l):  
      assert len(l) > 0  
  
      if len(l) < 5:  
          return nlogn_median(l)  
  
      chunks = chunked(l, 5)  
      full_chunks = [chunk for chunk in chunks if len(chunk) == 5]  
      sorted_groups = [sorted(chunk) for chunk in full_chunks]  
      medians = [chunk[2] for chunk in sorted_groups]  
      median_of_medians = quickselect_median(medians, pick_pivot)  
      return median_of_medians  
  
  def chunked(l, chunk_size):  
      return [l[i:i + chunk_size] for i in range(0, len(l), chunk_size)]  
  

Ringkasan

• Algoritme quickselect dapat menemukan median dalam waktu linear jika memilih pivot yang tepat
• Algoritme median-of-medians adalah metode pemilihan pivot yang menjamin waktu linear bahkan dalam kasus terburuk
• Dalam praktiknya, pemilihan pivot acak biasanya sudah cukup efektif

Ringkasan GN⁺

• Artikel ini menjelaskan berbagai algoritme untuk menemukan median, terutama metode untuk menemukannya dalam waktu linear
• Algoritme quickselect cepat secara rata-rata, tetapi algoritme median-of-medians dapat digunakan untuk mengantisipasi kasus terburuk
• Dalam penerapan nyata, pemilihan pivot acak biasanya sudah cukup efektif
• Algoritme dengan fungsi serupa antara lain introselect, yang digunakan di pustaka standar C++

[GN⁺]

Opini Hacker News

• Empat tahun lalu menulis artikel panjang yang membandingkan berbagai algoritme median
• 10-15 tahun lalu, menggunakan MapReduce untuk menemukan median dari entri log yang berisi miliaran nilai
  • Jika mengetahui presisi dan rentang data, penyortiran bucket bisa digunakan
  • Dengan merepresentasikan timing sebagai milidetik bilangan bulat dan membuat histogram, median bisa ditemukan dengan mudah
• Pada 2017, terbit makalah yang membuat pendekatan median-of-medians kompetitif dibanding algoritme selection lainnya
  • Andrei Alexandrescu membawakan ceramah tentang algoritme ini pada 2016
• Daftar penulis algoritme median-of-medians sangat terkenal
  • Manuel Blum, Robert Floyd, Ron Rivest, Bob Tarjan, Vaughan Pratt, dan lainnya
• Algoritme Floyd-Rivest juga efisien, tetapi sulit dipahami
• Dengan algoritme streaming, pendekatan perkiraan bisa dihitung tanpa menyimpan seluruh data di memori
• Ada cara memilih median dengan memodifikasi quicksort
• Pernah mendapat pertanyaan wawancara tentang mencari median dari daftar berisi triliunan angka
  • Menggunakan pendekatan menetapkan batas atas dan batas bawah untuk mencari median, tetapi itu bukan cara terbaik
  • Ada metode yang lebih efisien menggunakan priority heap
  • Setelah itu mulai berlangganan LeetCode
• Membagikan contoh sederhana yang diimplementasikan dalam Go
• Radix sort bisa digunakan untuk berbagai tipe data selain bilangan bulat, seperti string