Cari median array disortir di

Untuk menemukan median array yang tidak disortir, kita dapat membuat min-heap dalam waktu untuk elemen, dan kemudian kita dapat mengekstraksi satu per satu elemen untuk mendapatkan median. Tetapi pendekatan ini akan membutuhkan waktu . $O(n\log n)$ $n$ $n/2$ $O(n \log n)$

Bisakah kita melakukan hal yang sama dengan beberapa metode dalam waktu ? Jika kita bisa, lalu bagaimana caranya? $O(n)$

algorithms time-complexity Luv
sumber

en.wikipedia.org/wiki/Selection_algorithm

Jukka Suomela

@JukkaSuomela Mengapa tidak membuat ini jawaban yang cepat dan sederhana (dengan penjelasan singkat tentang satu algoritma seperti itu, idealnya)?

Raphael

Perhatikan diskusi meta terkait ; ternyata, pencarian web sederhana mengarah ke jawaban untuk pertanyaan ini.

Raphael

stackoverflow.com/questions/2571358/median-of-a-billion-numbers

Evgeny

Jawaban:

Ini adalah kasus khusus dari algoritma seleksi yang dapat menemukan th elemen terkecil dari sebuah array dengan adalah setengah dari ukuran array. Ada implementasi yang linier dalam kasus terburuk. $k$ $k$

Algoritma seleksi generik

Pertama mari kita lihat suatu algoritma find-kthyang menemukan th elemen terkecil dari sebuah array: $k$

find-kth(A, k)
  pivot = random element of A
  (L, R) = split(A, pivot)
  if k = |L|+1, return pivot
  if k ≤ |L|  , return find-kth(L, k)
  if k > |L|+1, return find-kth(R, k-(|L|+1))

Fungsi split(A, pivot)mengembalikan L,Rsedemikian rupa sehingga semua elemen di Rlebih besar daripada pivotdan Lyang lainnya (minus satu kemunculan pivot). Kemudian semua dilakukan secara rekursif.

$O(n)$ $O(n^2)$

Kasus terburuk linier: algoritma median-of-median

Pivot yang lebih baik adalah median semua median sub array Aukuran 5, dengan menggunakan prosedur memanggil pada larik median ini.

find-kth(A, k)
  B = [median(A[1], .., A[5]), median(A[6], .., A[10]), ..]
  pivot = find-kth(B, |B|/2)
  ...

$O(n)$

Perhatikan bahwa sebagian besar waktu menggunakan pivot acak lebih cepat.

jmad
sumber

Apakah ini ukuran 5standar? Bagaimana jika ukuran A kurang dari 5?

Jayesh

Untuk n tetap apa pun, kompleksitasnya konstan, kecuali tidak terbatas. Jadi, Anda dapat menggunakan algoritme apa pun yang valid dengan kerumitan hingga untuk kasus khusus seperti itu, meskipun itu O (2 ^ n). Untuk n tetap (yaitu paling banyak 4 dalam kasus keluar), kompleksitasnya paling banyak O (2 ^ 4) = O (1).

v6ak

Pada algoritma pertama: return A[k]tidak benar (kecuali Adiurutkan yang akan membuat algoritma diperdebatkan). Jika splitterjadi membagi Asehingga k = |L| + 1Anda masih tidak tahu di mana kelemen th. Kasing dasar Anda adalah kapan |A| = 1lagi Anda masih perlu melakukan salah satu dari dua panggilan rekursif.

wcochran

@NickCaplinger diperbaiki menggunakan web.archive.org

jmad

Bukankah kasus terburuk untuk algoritma pemilihan generik O (NlogN)? Bahkan jika panggilan rekursif hanya menyisakan 10% dari array setelah setiap panggilan, maka itu masih logaritma dasar 10.

oktavan

$n^{-1/4}$ $O(n)$

Ide utama dari algoritma ini adalah menggunakan sampling. Kita harus menemukan dua elemen yang berdekatan dalam urutan susunan array dan yang memiliki median terletak di antara mereka. Lihat referensi [MU2017] untuk diskusi lengkap.

[MU2017] Michael Mitzenmacher dan Eli Upfal. "Probabilitas dan Komputasi: Pengacakan dan Teknik Probabilistik dalam Algoritma dan Analisis Data," bab 3, halaman 57-62. Cambridge University Press, Edisi kedua, 2017.

zdm
sumber