Properti dan aplikasi struktur data, seperti batas bawah ruang, atau kompleksitas waktu penyisipan dan penghapusan objek.
Sejak buku Chris Okasaki tahun 1998 "Struktur data murni fungsional", saya belum melihat terlalu banyak struktur data fungsional murni yang menarik muncul; Saya dapat menyebutkan beberapa saja: IntMap (juga ditemukan oleh Okasaki pada tahun 1998, tetapi tidak ada dalam buku itu) Pohon jari (dan...
Paul Erdos berbicara tentang "Buku" di mana Tuhan menyimpan bukti paling elegan dari setiap teorema matematika. Ini bahkan mengilhami buku (yang saya percaya sekarang dalam edisi ke-4): Bukti dari Buku . Jika Tuhan memiliki buku yang serupa untuk algoritma, menurut Anda algoritma apa yang akan...
Apa saja beberapa algoritma utilitas yang sah yang terlalu rumit untuk diterapkan? Biarkan saya menjadi jelas: Saya tidak mencari algoritma seperti algoritma multiplikasi matriks optimal asimptotik saat ini (Coppersmith-Winograd), yang masuk akal untuk diimplementasikan tetapi memiliki konstanta...
Latar Belakang Beberapa tahun yang lalu, ketika saya masih sarjana, kami diberi pekerjaan rumah tentang analisis diamortisasi. Saya tidak dapat menyelesaikan salah satu masalah. Saya telah menanyakannya dalam teori comp.the , tetapi tidak ada hasil yang memuaskan muncul. Saya ingat kursus TA...
Dua cara menganalisis efisiensi suatu algoritma adalah untuk menempatkan batas atas asimptotik pada runtime, dan untuk menjalankannya dan mengumpulkan data eksperimental. Saya ingin tahu apakah ada kasus yang diketahui di mana ada kesenjangan yang signifikan antara (1) dan (2). Maksud saya,...
Pertanyaan ini terinspirasi oleh pertanyaan lain tentang apa yang baru dalam PFDS sejak penerbitan buku Okasaki pada tahun 1998 . Saya akan mulai dengan dua pertanyaan yang saya miliki: Apakah ada struktur data set fungsional murni yang mendekati kecepatan tabel hash? Mencoba belum ada di...
Saya mencari sumber set data besar untuk menguji beberapa implementasi algoritma grafik. Harap berikan juga informasi tentang jenis / distribusi (mis. Diarahkan / tidak diarahkan, sederhana / tidak sederhana, berbobot / tidak berbobot) dari grafik di sumber jika
Saya ingin tahu apakah ada cara untuk menyimpan hash multi-set bilangan bulat yang memiliki properti berikut, idealnya: Ini menggunakan O (1) ruang Ini dapat diperbarui untuk mencerminkan penyisipan atau penghapusan dalam waktu O (1) Dua koleksi yang identik (yaitu, koleksi yang memiliki elemen...
Sebagian besar algoritma terkenal adalah urutan pertama, dalam arti bahwa input dan outputnya adalah data "biasa". Beberapa di antaranya adalah urutan kedua dengan cara sepele, misalnya menyortir, hashtable atau fungsi peta dan lipat: semuanya di-parameterkan oleh suatu fungsi, tetapi mereka tidak...
Jadi, filter Bloom cukup keren - mereka adalah set yang mendukung pemeriksaan keanggotaan tanpa negatif palsu, tetapi kemungkinan kecil positif palsu. Namun baru-baru ini, saya menginginkan "filter Bloom" yang menjamin yang sebaliknya: tidak ada positif palsu, tetapi berpotensi negatif...
Apakah ada struktur data yang mengambil array yang tidak berurutan dari item, melakukan preprocessing di O ( n ) dan menjawab pertanyaan: apakah ada beberapa elemen x dalam daftar, setiap query dalam waktu terburuk O ( log n ) ?nnnO ( n )O(n)O(n)xxxO ( logn )O(logn)O(\log n) Saya benar-benar...
Saya memiliki beberapa pengalaman dalam komputasi ilmiah, dan telah banyak menggunakan pohon kd untuk aplikasi BSP (partisi ruang biner). Saya baru-baru ini menjadi lebih akrab dengan oktri, struktur data yang mirip untuk mempartisi ruang Euclidean 3-D, tetapi yang bekerja pada interval tetap yang...
Apakah ada struktur data antrian prioritas yang mendukung operasi berikut? Sisipkan (x, p) : Tambahkan catatan baru x dengan prioritas p StableExtractMin () : Kembalikan dan hapus catatan dengan prioritas minimum, putuskan hubungan dengan urutan penyisipan . Jadi, setelah Sisipan (a, 1),...
Misalkan saya memiliki poset "S" dan predikat monoton "P" pada S. Saya ingin menemukan satu atau semua elemen maksimal dari S yang memuaskan P. EDIT : Saya tertarik dalam meminimalkan jumlah evaluasi P . Algoritma apa yang ada untuk masalah ini dan properti serta operasi tambahan apa yang mereka...
Saya belum berhasil menemukan struktur data ini, tetapi saya bukan ahli di bidang ini. Struktur mengimplementasikan himpunan, dan pada dasarnya adalah array elemen yang sebanding dengan invarian. Yang invarian adalah sebagai berikut (didefinisikan secara rekursif): Array dengan panjang 1 adalah...
Saya perlu menghitung median berjalan: Input: , k , vektor ( x 1 , x 2 , ... , x n ) .nnnkkk( x1, x2, ... , xn)(x1,x2,…,xn)(x_1, x_2, \dotsc, x_n) Output: vektor , di mana y i adalah median dari ( x i , x i + 1 , ... , x i + k - 1 ) .( y1, y2, ... , yn - k + 1)(y1,y2,…,yn−k+1)(y_1, y_2, \dotsc,...
Saya mencari buku tentang struktur data tingkat lanjut yang melampaui apa yang dicakup dalam buku teks standar seperti Cormen, Leiserson, Rivest, dan "Pengantar Algoritma" Stein. Sebuah buku yang dapat digunakan untuk mengajar kursus tingkat pascasarjana tentang struktur data tingkat lanjut...
Apakah ada analog paralel alami dengan pohon merah-hitam dengan sifat yang sama atau bahkan tidak terlalu buruk untuk pembaruan sementara cukup efisien dalam bekerja? Secara umum, apa yang terbaik yang dapat kita lakukan untuk pencarian paralel dengan pembaruan?
x∈Rnx∈Rnx \in \mathbb{R}^n∥x∥0<k‖x‖0<k\|x\|_0 < kA R nAxAxAxAAARRRnnnR≪nR≪nR \ll nAAAkkk-Sparse dengan sekecil . Saya mungkin tidak memiliki parameter yang paling dikenal tetapi ini adalah ide umum.R O ( k n o ( 1 ) )xxxRRRO(kno(1))O(kno(1))O(k n^{o(1)}) Pertanyaan saya adalah: apakah ada...
Apa yang diketahui tentang struktur data yang dapat mempertahankan urutan item yang tunduk pada dua operasi berikut? Tekan (x): tambahkan x ke akhir urutan, dan kembalikan pengidentifikasi untuk posisinya di urutan Ekstrak (S): diberi seperangkat pengidentifikasi yang tidak berurutan, menghapus...