Menggunakan algoritma Fibonacci rekursif berikut: def fib(n): if n==0: return 0 elif n==1 return 1 return (fib(n-1)+fib(n-2)) Jika saya memasukkan angka 5 untuk menemukan fib (5), saya tahu ini akan menghasilkan 5 tetapi bagaimana saya memeriksa kompleksitas algoritma ini? Bagaimana cara...
Harap pertimbangkan loop bertingkat tiga berikut: for (int i = 1; i <= n; ++i) for (int j = i; j <= n; ++j) for (int k = j; k <= n; ++k) // statement Pernyataan di sini dijalankan dengan tepat n(n+1)(n+2)6n(n+1)(n+2)6n(n+1)(n+2)\over6 kali. Bisakah seseorang tolong jelaskan bagaimana...
Saya percaya ini benar tetapi belum bisa mendapatkan bukti formal juga. Tetapi apakah benar bahwa spanning tree minimum dapat dicapai dengan menerapkan algoritma Kruskal? Demikian pula, apakah ini benar untuk algoritma Prim? EDIT: Untuk lebih tepatnya, saya ingin tahu jika diberi MST untuk grafik...
Fungsi heuristik h(n)h(n)h (n) adalah ... Konsisten jika perkiraan biaya dari node nnn ke tujuannya adalah tidak lebih besar dari langkah biaya penggantinya n′n′n' ditambah perkiraan biaya dari penerus tujuan. Diperbolehkan jika h(n)h(n)h(n) tidak pernah melebih-lebihkan biaya sebenarnya untuk...
Saya membaca buku tentang topik ilmu komputer tetapi tidak memiliki beberapa latar belakang prasyarat. Biasanya ketika saya mengalami istilah yang saya tidak mengerti, saya hanya mencarinya, tetapi untuk Pencarian Universal saya belum bisa menemukan penjelasan yang cocok untuk pembaca tanpa latar...
Bruinier dan Ono telah menemukan formula aljabar untuk fungsi partisi , yang secara luas dilaporkan sebagai terobosan. Saya tidak dapat memahami makalah ini, tetapi apakah ia memiliki konsekuensi algoritmik untuk penghitungan cepat fungsi
Saya mencari algoritma O (V + E) untuk menemukan reduksi transitif yang diberikan DAG. Yaitu menghapus sebanyak mungkin tepi sehingga jika Anda dapat mencapai v dari Anda, untuk v dan Anda sewenang-wenang, Anda masih dapat mencapai setelah menghilangkan tepi. Jika ini adalah masalah standar,...
Tampaknya saya telah menemukan cara umum untuk mengubah prosedur rekursif apa pun menjadi rekursi ekor: Tentukan sub-prosedur pembantu dengan parameter "hasil" tambahan. Terapkan apa yang akan diterapkan pada nilai pengembalian prosedur ke parameter itu. Hubungi prosedur bantuan ini untuk...
Saya mencari algoritma yang efisien untuk masalah berikut atau bukti NP-hardness. Biarkan menjadi himpunan dan seperangkat himpunan bagian dari . Temukan urutan panjang paling sedikit sehingga untuk setiap , ada sedemikian rupa sehingga .Σ\SigmaA⊆P(Σ)A\subseteq\mathcal{P}(\Sigma)Σ\Sigmaw∈Σ∗w\in...
Ketika melakukan kalkulus mental, seseorang dapat melakukannya: Dengan bilangan bulat k, jumlahkan semua digit (pada basis 10), dan jika hasilnya kelipatan 3, maka k adalah kelipatan 3. Apakah Anda tahu ada algoritma yang bekerja sama tetapi beroperasi pada digit angka biner (bit)? Pada...
Diberikan dua string bagaimana Anda bisa memeriksa apakah mereka permutasi satu sama lain menggunakan ruang O (1)? Memodifikasi string tidak diizinkan dengan cara apa pun. Catatan: O (1) spasi dalam kaitannya dengan panjang string DAN ukuran
Misalkan saya memiliki grafik dengan M ( G ) yang (tidak diketahui) set matching sempurna G . Misalkan set ini tidak kosong, lalu seberapa sulitkah untuk mengambil sampel secara acak dari M ( G ) ? Bagaimana jika saya baik-baik saja dengan distribusi yang dekat dengan seragam, tetapi tidak cukup...
Saya baru saja menemukan kalimat ini di halaman 6 dari Garey and Johnson's "Computers and Intractability". Algoritma apa pun yang fungsi kompleksitas waktunya tidak dapat dibatasi disebut algoritma waktu eksponensial (walaupun harus dicatat bahwa definisi ini mencakup fungsi kompleksitas waktu...
Halaman wikipedia tentang algoritma perkalian menyebutkan yang menarik oleh Donald Knuth . Pada dasarnya, ini melibatkan penggabungan fourier-transform multiplication dengan tabel pra-komputasi dari perkalian berukuran logaritmik. Ini berjalan dalam waktu linier. Artikel tersebut bertindak seperti...
Dari apa yang saya baca di preliminary version of a chapter of the book “Lectures on Scheduling” edited by R.H. M¨ohring, C.N. Potts, A.S. Schulz, G.J. Woeginger, L.A. Wolsey, to appear around 2011 A.D. Ini adalah Definisi PTAS : Skema aproksimasi waktu polinomial ( PTAS ) untuk masalah adalah...
Ada nnn sampah, yang bin th mengandung bola. Bola memiliki warna, ada bola warna . Biarkan .iiiaiaia_innnaiaia_iiiim=∑ni=1aim=∑i=1naim=\sum_{i=1}^n a_i Swap adalah mengambil bola dari satu nampan dan menukar dengan bola dari nampan lain. Kami ingin jumlah swap minimum sehingga setiap nampan hanya...
Saya telah diberi masalah berikut dalam sebuah wawancara (yang telah saya gagal pecahkan, tidak mencoba menipu jalan saya sebelumnya): Permainan dimulai dengan bilangan bulat positif . (Mis. A 0 = 1234. ) Angka ini dikonversi ke representasi biner, dan N adalah jumlah bit yang ditetapkan ke 1 ....
Saya mencoba memecahkan 25k klausa 5k variabel masalah SAT. Karena sudah berjalan selama satu jam (precosat) dan saya ingin menyelesaikan yang lebih besar setelah itu, saya mencari SAT-Solver multi-core. Karena sepertinya ada banyak SAT-Solver, saya sangat tersesat. Adakah yang bisa menunjukkan...
Jarak edit Levenshtein-Distance antara daftar adalah masalah yang dipelajari dengan baik. Tetapi saya tidak dapat menemukan banyak perbaikan yang mungkin jika diketahui bahwa tidak ada elemen yang muncul lebih dari satu kali di setiap daftar . Mari kita asumsikan juga bahwa elemen-elemennya...
Saya memiliki pohon tidak berarah yang simpulnya ingin saya beri label. Node daun harus diberi label satu. Lalu, anggap daunnya sudah dibuang. Di pohon yang tersisa, daunnya harus diberi label dua. Proses ini berlanjut dengan cara yang jelas sampai semua simpul memiliki label. Alasan saya melakukan...