Dalam tulisan Complexity of the Frobenius Problem oleh Ramírez-Alfonsín, masalah terbukti sebagai NP-complete menggunakan pengurangan Turing. Apakah itu mungkin? Bagaimana sebenarnya? Saya pikir ini hanya mungkin dengan pengurangan banyak waktu polinomial. Apakah ada referensi tentang ini? Apakah...
Saya mencari contoh masalah yang memiliki batas bawah ) untuk input .Ω(|x|2Ω(|x|2\Omega(|x|^2xxx Masalahnya perlu memiliki properti berikut: Ω(n2)Ω(n2)\Omega(n^2) bukti runtime untuk algoritma apa pun - prioritas pertama adalah memiliki sesederhana mungkin argumen batas
Mari kita pertimbangkan segmen memori (yang ukurannya dapat tumbuh atau menyusut, seperti file, bila diperlukan) di mana Anda dapat melakukan dua operasi alokasi memori dasar yang melibatkan blok ukuran tetap: alokasi satu blok membebaskan blok yang sebelumnya dialokasikan yang tidak digunakan...
Saat memikirkan satu masalah, saya menyadari bahwa saya perlu membuat algoritma yang efisien untuk menyelesaikan tugas berikut: Masalahnya: kita diberi kotak persegi dua dimensi dari sisi nnn yang sisi-sisinya sejajar dengan sumbu. Kita bisa melihatnya dari atas. Namun, ada juga mmm segmen...
Saya membaca bahwa algoritma yang paling efisien ditemukan dapat menghitung faktor dalam waktu, tetapi kode saya tulis adalah O ( n ) atau mungkin tergantung pada seberapa cepat pembagian dan modulus. Saya cukup yakin saya telah salah mengerti sesuatu di suatu tempat, tapi saya tidak yakin di mana....
Dalam praktiknya saya memahami bahwa setiap rekursi dapat ditulis sebagai loop (dan sebaliknya (?)) Dan jika kita mengukur dengan komputer aktual kita menemukan bahwa loop lebih cepat daripada rekursi untuk masalah yang sama. Tetapi apakah ada teori yang membuat perbedaan ini atau apakah itu...
Kita mengatakan bahwa bahasa adalah padat jika ada polinomial p sehingga | J c ∩ Σ n | ≤ p ( n ) untuk semua n ∈ N . Dengan kata lain, untuk setiap panjang n yang diberikan hanya ada banyak kata panjang n secara polinomi yang tidak ada dalam JJ⊆Σ∗J⊆Σ∗J \subseteq
Dalam buku "Komputasi Geometri: Algoritma dan Aplikasi" oleh Mark de Berg et al., Ada algoritma brute force yang sangat sederhana untuk menghitung triangulasi Delaunay. Algoritme menggunakan gagasan tepi ilegal - tepi yang mungkin tidak muncul dalam triangulasi Delaunay yang valid dan harus diganti...
Sebuah posting blog teka - teki baru - baru ini tentang menemukan tiga yang berjarak sama rata membawa saya ke pertanyaan stackoverflow dengan jawaban teratas yang mengklaim melakukannya dalam waktu O (n lg n). Bagian yang menarik adalah solusinya melibatkan mengkuadratkan polinomial,...
Algoritma waktu semu-polinomial adalah algoritma yang memiliki waktu berjalan polinomial pada nilai input (besarnya) tetapi waktu berjalan eksponensial pada ukuran input (jumlah bit). Misalnya menguji apakah angka nnn adalah prima atau tidak, memerlukan perulangan angka dari 2 ke dan memeriksa...
Misalkan kita diberi dua angka dan dan kita ingin menemukan untuk l \ le i, \, j \ le r .lllrrrmax(i⊕j)max(i⊕j)\max{(i\oplus j)}l≤i,j≤rl≤i,j≤rl\le i,\,j\le r Algoritma naif hanya memeriksa semua pasangan yang mungkin; misalnya dalam ruby, kita akan memiliki: def max_xor(l, r) max = 0...
Untuk mengukur kompleksitas suatu algoritma, apakah itu kompleksitas waktu, atau kompleksitas komputasi? Apa perbedaan di antara mereka? Saya biasa menghitung jumlah maksimum (terburuk) operasi dasar (paling mahal) dalam
Saya memiliki sekelompok set n yang saya butuhkan untuk menghitung semacam nilai "keunikan" atau "kesamaan". Saya telah menetapkan indeks Jaccard sebagai metrik yang cocok. Sayangnya, indeks Jaccard hanya beroperasi pada dua set sekaligus. Untuk menghitung kesamaan antara semua set , itu akan...
misal ?xy+x+y=x+y(x+1)xy+x+y=x+y(x+1)xy+x+y=x+y(x+1) Ekspresi berasal dari aljabar sekolah menengah biasa, tetapi terbatas pada penambahan dan perkalian aritmatika (misalnya ), tanpa inversi, pengurangan atau pembagian. Surat adalah variabel.2+2=4;2.3=62+2=4;2.3=62+2=4; 2.3=6 Jika ini membantu,...
Saya tertarik dalam menghitung nnn 'th kekuatan dari matriks . Misalkan kita memiliki algoritma untuk perkalian matriks yang berjalan dalam waktu . Kemudian, orang dapat dengan mudah menghitung dalam waktu. Apakah mungkin untuk menyelesaikan masalah ini dalam kompleksitas waktu yang lebih rendah?n...
Saya ingin memastikan bahwa ini adalah bagian dari pekerjaan rumah saya untuk kursus yang sedang saya ikuti. Saya mencari bantuan dalam melanjutkan, BUKAN JAWABAN. Ini pertanyaannya: 5-menunjuk-bintang dalam grafik tidak terarah adalah 5-klik. Tunjukkan bahwa 5-POINTED-STAR , di mana...
Misalkan kita diberi bilangan bulat yang berbeda , sehingga untuk beberapa konstanta , dan untuk semua .a 1 , a 2 , … , a n 0 ≤ a i ≤ knnna1,a2,…,anSebuah1,Sebuah2,...,Sebuahna_1, a_2, \dots, a_nk > 00≤ai≤kn0≤Sebuahsaya≤kn0 \le a_i \le knk>0k>0k \gt 0isayai Kami tertarik untuk menemukan...
Masalah Diberikan mesin Turing yang telah dikenal runtime O ( g ( n ) ) sehubungan dengan panjang input n , apakah runtime dari M ∈ O ( f ( n ) ) ?M.M.MO (g( n ) )HAI(g(n)){O}(g(n))nnnM.∈ O ( f( n ) )M.∈HAI(f(n))M \in {O}(f(n)) Apakah masalah di atas dapat diputuskan untuk beberapa pasangan...
Inilah masalah yang sudah diketahui. Diberikan array A [ 1 ... n ]A[1...n]A[1\dots n] dari bilangan bulat positif, menghasilkan bilangan bulat positif terkecil tidak dalam array. Masalah dapat diselesaikan dalam O ( n )HAI(n)O(n) ruang dan waktu: membaca array, keep track di O ( n )HAI(n)O(n)...
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...