Saya membaca sebuah pertanyaan, dan saya mencari masukan tentang bagaimana menyelesaikannya:
Angka-angka secara acak dihasilkan dan disimpan ke dalam array (memperluas), Bagaimana Anda melacak median?
Ada dua struktur data yang bisa menyelesaikan masalah. Satu adalah pohon biner seimbang, yang lain adalah dua tumpukan yang melacak bagian terbesar dan bagian terkecil dari elemen. Saya pikir dua solusi ini memiliki waktu berjalan yang sama O(n lg n), tetapi saya tidak yakin dengan penilaian saya.
Apa cara terbaik untuk melacak median?
Usaha saya:
Dalam pertanyaan ini, saya pikir tumpukan adalah cara terbaik untuk melacak median. Ada dua tumpukan, tumpukan besar dan tumpukan kecil, yang tidak perlu berurutan. Pertama, kami menghitung nilai rata-rata elemen dalam array. Jika elemen kurang dari nilai rata-rata, kami menempatkan num ke tumpukan kecil. Sebaliknya, kami menempatkan num ke tumpukan besar. Jika jumlah tumpukan besar sama dengan jumlah tumpukan kecil, yang terbesar di tumpukan kecil dan yang terkecil di tumpukan besar adalah median. Jika kedua tumpukan memiliki ukuran yang berbeda, kita cukup membuang elemen root dari tumpukan dengan ukuran lebih besar dan mendorongnya ke akar tumpukan ukuran yang lebih kecil. Untuk tumpukan besar, elemen akar adalah yang terkecil, dan untuk tumpukan kecil, elemen akar adalah yang terbesar. Dengan cara ini, jika kedua tumpukan memiliki ukuran yang sama atau perbedaan digital,
Saya pikir solusi ini memiliki waktu berjalan sebagai O (m * n), m berarti waktu kita menyesuaikan tumpukan tidak seimbang.
Apakah ini cara terbaik untuk melacak median?
sumber
std::nth_elementsiapa saja?Jawaban:
Mungkin ada lebih dari 2 struktur data yang mengatasi masalah ini. Lihatlah Perkiraan Median dan Jumlah lain dalam Satu Pass dan dengan Memori Terbatas
Mereka tidak menggunakan dua tumpukan. Saya membayangkan Anda bisa memodifikasi algoritme mereka untuk mendapatkan nilai perkiraan median berjalan secara berkala. Seberapa baik suatu pendekatan tentu saja, tergantung pada banyak faktor, tidak terkecuali berapa banyak data yang telah melewati algoritma.
sumber
Solusi yang lebih baik adalah dengan menggunakan daftar lewati. Karena daftar yang akan Anda sisipkan selalu dipertahankan sebagai daftar yang disortir (berdasarkan fakta bagaimana Anda membangunnya), kompleksitas penyisipan adalah O (log n). Anda akan mengambil keuntungan dari fakta bahwa penyisipan pertama memberi Anda median dengan biaya nol (item yang dimasukkan adalah median). Setelah setiap penyisipan tambahan, daftar Anda masih diurutkan, dan median itu sendiri akan melayang naik atau turun dengan indeks tunggal, dan perbandingan ini adalah O (1).
Total kompleksitas = O (log n)
sumber
O(log n)- memasukkan n elemen memiliki kompleksitasO(n log n)Bahkan Anda dapat menemukan median dalam O (n) operasi hanya melalui menemukan k th jumlah terkecil dalam daftar, :) melihat ke Median dari median algoritma seleksi untuk rincian.
sumber