Apakah ada masalah yang semakin mudah karena ukurannya bertambah?

62

Ini mungkin pertanyaan yang menggelikan, tetapi mungkinkah memiliki masalah yang sebenarnya semakin mudah saat input bertambah besar? Saya ragu ada masalah praktis seperti ini, tetapi mungkin kita dapat menemukan masalah yang merosot yang memiliki properti ini. Sebagai contoh, mungkin ia mulai "memecahkan dirinya sendiri" ketika menjadi lebih besar, atau berperilaku dengan cara yang aneh lainnya.

algorithms asymptotics dsaxton
sumber

7

Salah satu masalah nyata dengan properti ini yang muncul dalam pikiran adalah password hash crack yang murni ketika dirumuskan seperti "diberikan n hash, crack setidaknya satu hash". Karena kecepatan retak akan skala secara linear dengan n, waktu berjalan akan sebanding dengan 1 / n - kecuali bahwa kita tidak dapat benar-benar menetapkan waktu yang pasti karena retak adalah stokastik dan tidak memiliki batas atas waktu yang konstan.

amon

1

@amon Waktu berjalan tidak berskala seperti . Dibutuhkan waktu hanya untuk membaca hash Anda telah diberikan sebagai masukan!

1 / n

$1/n$

n

$n$

n

$n$

David Richerby

3

Apakah yang Anda maksud lebih mudah secara absolut atau relatif? Ukuran biaya manakah yang Anda izinkan? Apakah Anda memerlukan pengurangan biaya secara ketat, atau tidak meningkat (dari titik tertentu) cukup?

Raphael

2

@ DavidRicherby Dalam contoh ini, adalah sah untuk mengabaikan biaya membaca input selama saya tidak membuat pernyataan tentang biaya absolut. Sebaliknya, kecepatan meningkat secara linier dengan input. Oleh karena itu, n • T (1)> T (n) bahkan ketika mempertimbangkan biaya untuk membaca input. Yaitu untuk masalah ini lebih mudah untuk menyelesaikan input besar sekaligus daripada membagi input, meskipun masalahnya dapat dibagi. Saya tidak mengatakan bahwa T (n)> T (n +1) untuk semua n.

Amon

4

Untuk semua orang yang ingin memposting jawaban lain dari formulir, "Beberapa masalah di mana input adalah pertanyaan plus banyak petunjuk tentang jawabannya": Ini tidak berfungsi. Input tersulit dari panjang adalah input di mana Anda menggunakan semua bit untuk mengajukan pertanyaan dan tidak memberikan petunjuk. Fakta bahwa mudah untuk berurusan dengan pertanyaan pendek dengan banyak petunjuk tidak berarti waktu berjalan terburuk adalah baik.

n

$n$

n

$n$

David Richerby

39

Tidak, itu tidak mungkin: setidaknya, tidak dalam arti asimptotik, di mana Anda memerlukan masalah untuk terus menjadi lebih mudah, selamanya, seperti . $n \to \infty$

Biarkan menjadi waktu berjalan terbaik untuk menyelesaikan masalah seperti itu, di mana adalah ukuran input. Perhatikan bahwa waktu berjalan adalah hitungan dari jumlah instruksi yang dieksekusi oleh algoritma, sehingga harus berupa bilangan bulat non-negatif. Dengan kata lain, untuk semua . Sekarang jika kita mempertimbangkan fungsi , kita melihat tidak ada fungsi seperti itu yang menurun secara monoton. (Apa pun adalah, ia harus terbatas, katakanlah ; tetapi kemudian karena secara monoton menurun secara ketat, dan $T(n)$ $n$ $T(n) \in \mathbb{N}$ $n$ $T: \mathbb{N} \to \mathbb{N}$ $T(0)$ $T(0)=c$ $T$ $T(c) \le 0$ $T(c+1) \le -1$ , yang tidak mungkin.) Untuk alasan yang sama, tidak ada fungsi yang menurun secara asimptotik: kita dapat membuktikan bahwa tidak ada fungsi waktu berjalan mana terdapat sehingga untuk semua , menurun secara monoton (fungsi semacam itu pada akhirnya harus menjadi negatif). $T(n)$ $n_0$ $n \ge n_0$ $T(n)$

Jadi, masalah seperti itu tidak bisa ada, karena alasan sederhana bahwa waktu berjalan harus bilangan bulat non-negatif.

Perhatikan bahwa jawaban ini hanya mencakup algoritme deterministik (yaitu, waktu berjalan terburuk). Itu tidak mengesampingkan kemungkinan algoritma acak yang waktu berjalannya diharapkan secara monoton menurun, selamanya. Saya tidak tahu apakah mungkin ada algoritma seperti itu. Saya berterima kasih kepada Beni Cherniavsky-Paskin untuk pengamatan ini .

DW
sumber

9

Ini adalah bukti yang bagus, tapi saya tidak setuju dengan premis. Alih-alih meminta runtime yang benar-benar menurun secara monoton, pertanyaannya mungkin lebih masuk akal membutuhkan fungsi di mana ada a, b dengan a <b sehingga T (a)> T (b), yaitu non-ketatnya yang menurun secara monoton. Kemudian, tentu saja mungkin untuk menemukan fungsi integer yang sesuai. Tapi mengapa bilangan bulat? Saya mendapat kesan bahwa waktu berjalan menunjukkan waktu, bukan penghitungan instruksi (kecuali tentu saja untuk mesin Turing), dan bahwa ekspresi T dapat menggunakan operasi non-integer seperti log () atau eksponen non-integer.

amon

2

@amon "waktu berjalan menunjukkan waktu, bukan jumlah instruksi" Sama sekali tidak. Waktu berjalan selalu merupakan hitungan instruksi. Ada hal lain yang tidak mungkin untuk dipikirkan karena akan tergantung pada banyak detail implementasi yang tidak layak.

David Richerby

3

Meskipun pertanyaannya tidak jelas, saya tidak melihat bagaimana itu mengecualikan fungsi biaya, katakanlah, . Sekarang, tetapi untuk "small" , jadi masalahnya "semakin mudah", secara relatif. (Biaya mutlak tumbuh tanpa gejala, tentu saja).

T (n) = n^{2} \cdot (1 + ϵ)^{- n} + n

$T(n) = n^2 \cdot (1+\epsilon)^{-n} + n$

T (n) \sim n

$T(n) \sim n$

T (n) \approx n^{2}

$T(n) \approx n^2$

n

$n$

Raphael

2

@Raphael, bukan masalah semakin mudah: semakin besar karena semakin besar, sehingga masalahnya semakin sulit karena semakin besar, begitu cukup besar. Saya menyatakan dalam kalimat pertama jawaban saya bahwa tidak ada masalah yang bisa terus menjadi lebih mudah selamanya. Tentu saja, masalah bisa menjadi lebih mudah untuk sementara waktu ( dapat menurun untuk , katakanlah), tetapi tetapi itu tidak dapat terus menjadi lebih mudah selamanya.

T (n) \sim n

$T(n) \sim n$

T (n)

$T(n)$

n

$n$

n

$n$

n

$n$

T (n)

$T(n)$

n \leq c

$n \le c$

DW

1

Bahkan dengan waktu bilangan bulat, untuk algoritma acak , waktu yang diharapkan (atau ukuran distribusi lainnya) dapat fraksional, dan secara bertahap dapat mendekati beberapa konstanta dari atas. [Ini tidak berarti masalah tersebut benar-benar ada, hanya bahwa "tidak ada fungsi seperti ada" argumen tidak cukup.]

T

$T$

Beni Cherniavsky-Paskin

25

Meskipun ini bukan jawaban untuk pertanyaan Anda, algoritma pencarian string Boyer-Moore mendekati. Seperti yang dikatakan Robert Moore di halaman webnya tentang algoritma,

Algoritme kami memiliki sifat khusus yang, secara kasar, semakin panjang polanya, semakin cepat pula algoritmanya.

Dengan kata lain, secara umum algoritma mencari instance string target dalam string sumber dan untuk string sumber tetap, semakin lama string target, semakin cepat algoritma berjalan.

Rick Decker
sumber

10

Bisa dibilang, polanya bukan ukuran masalahnya melainkan panjang string yang dicari. Seperti dalam komentar David Richerby di atas , saya berpendapat bahwa panjang pola lebih merupakan petunjuk tentang bagaimana menyelesaikan masalah (mencari tentang string) daripada masalah itu sendiri (melihat apakah suatu pola cocok dengan string dengan panjang tertentu) .)

Kevin - Reinstate Monica

4

@Kevin Pernyataan itu menyarankan agar mencari pola panjang

panjangnya

teks lebih cepat daripada mencari pola

panjang

. Melihat input hubungan tetap seperti itu (yaitu pasangan string), saya pikir Rick telah memberikan jawaban yang cocok untuk pertanyaan (jika tidak dalam pengertian klasik, asimptotik).

\sqrt{n}

$\sqrt{n}$

n

$n$

\log n

$\log n$

Raphael

10

Jelas, dari sudut pandang matematika murni, algoritma CS murni ini tidak mungkin. Tetapi sebenarnya ada beberapa contoh dunia nyata ketika meningkatkan proyek Anda membuatnya lebih mudah, banyak yang tidak intuitif untuk pengguna akhir.

Petunjuk Arah : Semakin lama arah Anda, kadang-kadang petunjuk itu menjadi lebih mudah. Misalnya, jika saya ingin Google Maps memberi saya petunjuk untuk pergi ke barat 3.000 mil, saya bisa berkendara ke Pantai Barat - dan akan mendapatkan instruksi mengemudi lintas negara. Tetapi jika saya ingin pergi 6.000 mil ke barat, saya akan berakhir dengan instruksi yang jauh lebih sederhana: naik pesawat dari NYC ke Hokkaido. Memberi saya rute lintas negara yang menggabungkan lalu lintas, jalan, cuaca, dll. Algoritma agak sulit, tetapi mengatakan kepada saya untuk naik pesawat dan mencari penerbangan dalam database relatif jauh lebih sederhana. Grafik ASCII tingkat kesulitan vs jarak:

           |     /
           |    /
Difficulty |   /                  ____-------
           |  /           ____----
           | /    ____----
            ---------------------------------
                       Distance

Rendering : katakan saya ingin render satu wajah dan render 1000 wajah; ini untuk iklan baliho sehingga kedua gambar akhir harus 10000px oleh 5000px. Rendering satu wajah secara realistis akan sulit - pada resolusi beberapa ribu piksel Anda harus menggunakan mesin yang sangat kuat - tetapi untuk kerumunan 1000 wajah, setiap wajah hanya perlu sepuluh piksel, dan dapat dengan mudah dikloning! Saya mungkin bisa membuat 1000 wajah di laptop saya, tetapi merender wajah yang realistis dengan 10000px membutuhkan waktu yang sangat lama dan mesin yang kuat. Grafik ASCII tingkat kesulitan vs. objek yang diberikan, menunjukkan betapa sulitnya merender benda ke gambar dengan ukuran yang ditentukan turun dengan cepat tetapi kemudian kembali dengan lambat:

           | -    
           |- -                     _________
Difficulty |   --      ______-------            
           |     ------      
           |       
            ---------------------------------
                        Objects

Kontrol perangkat keras : banyak hal dengan perangkat keras menjadi lebih mudah. "Pindahkan motor X 1 derajat" sulit dan / atau tidak mungkin, dan Anda harus berurusan dengan semua hal yang Anda tidak harus berurusan dengan untuk "memindahkan motor X 322 derajat".

Tugas berdurasi pendek: Katakan Anda ingin item X aktif (jumlah waktu yang sangat kecil) setiap detik. Dengan meningkatkan jumlah waktu yang dijalankan X, Anda akan memerlukan perangkat lunak dan perangkat keras yang kurang kompleks.

Owen Versteeg
sumber

Dalam contoh "arah" Anda, sebutkan persis masalah komputasi dan apa instansinya. Sama sekali tidak jelas bagi saya bahwa contoh 6k miles Anda adalah contoh yang lebih besar atau hanya contoh dari bagian yang mudah dari sesuatu (misalnya, jika saya memberi Anda grafik terhubung grafik yang besar plus satu titik terisolasi, meminta jalur terpendek pada umumnya adalah "sulit" tetapi meminta jalur terpendek dari titik terisolasi ke mana saja itu sepele). Sekali lagi, untuk contoh rendering Anda, apa masalah komputasi yang sebenarnya? Apa contoh yang Anda ukur kompleksitasnya?

David Richerby

Contoh rendering tampaknya bukan contoh dari masalah yang sama: yang pertama adalah rendering gambar tunggal; yang kedua adalah merender banyak gambar kecil dan kemudian menempelkan banyak salinan dari gambar-gambar itu ke beberapa area.

David Richerby

Saya pikir wrt untuk melakukan perjalanan parameter akan menjadi nama 2 kota dan n akan menjadi jumlah karakter untuk mengkodekannya.

emory

3

Ada beberapa kasus. Mereka adalah kasus-kasus di mana kriteria keberhasilan adalah fungsi dari data, daripada mencoba untuk menemukan jawaban tunggal. Misalnya, proses statistik yang hasilnya diungkapkan dengan interval kepercayaan bisa menjadi lebih mudah.

Satu kasus khusus yang saya pikirkan adalah masalah yang memiliki transisi dari perilaku diskrit ke perilaku berkelanjutan, seperti aliran cairan. Memecahkan masalah kecil hingga dalam tingkat kesalahan dapat melibatkan pemodelan semua interaksi diskrit, yang mungkin membutuhkan superkomputer. Perilaku terus menerus sering mengizinkan penyederhanaan tanpa menghasilkan hasil di luar batas kesalahan terkait.

Cort Ammon
sumber

2

Pertanyaannya menarik dan BERMANFAAT, karena filosofi kami di bidang informatika adalah untuk menyelesaikan masalah, semakin banyak kita membaca semakin sulit. Tetapi, pada kenyataannya, PALING masalah yang disajikan dengan cara yang khas (sulit) dapat dengan mudah diwakili dalam cara "mudah"; bahkan mengetahui respons DW (yang salah mengingat bahwa mudah bukan berarti lebih cepat, berarti "kurang lambat"; sehingga Anda tidak harus menemukan waktu negatif, Anda harus menemukan waktu asimptotik).

Trik untuk menemukannya adalah menempatkan bagian dari solusi seperti petunjuk sebagai entri, dan mempertimbangkan entri masalah seperti parameter konstan.

Contoh: Apa cara terpanjang dalam mobil antara London dan Paris menghindari mengunjungi dua kali kota Perancis dan Inggris dan tidak mengunjungi negara lain? pertimbangkan, Anda harus pergi ke Birmingham sebelum Ashford, Orleans sebelum Versailles, La Rochelle sebelum Limoge, dll ...

Jelas bahwa masalah dengan entri panjang akan lebih mudah dengan entri pendek.

Contoh penggunaan: Bayangkan sebuah playgame yang dikelola oleh mesin, dan IA komputer harus menentukan apakah dia harus menjelajahi lebih dalam permainan untuk menemukan lebih banyak petunjuk atau yang lain, jika sekarang saatnya menyimpulkan apa keputusan terbaik yang harus diambil .

Juan Manuel Dato
sumber

2

Teladan Anda tidak berfungsi. Contoh yang besar karena mereka memiliki begitu banyak petunjuk sehingga petunjuk menentukan urutan linear dari simpul grafik memang mudah. Namun, contoh yang besar karena mereka memberikan grafik besar dengan hampir tidak ada petunjuk sama sulitnya dengan masalah jalur Hamilton biasa. Dengan demikian, waktu berjalan terburuk dari algoritma apa pun yang menyelesaikan masalah ini akan setidaknya sama buruknya dengan waktu berjalan terburuk dari algoritma terbaik untuk jalur Hamilton, yang sepertinya tidak "super mudah".

David Richerby

@ David, respons Anda sepenuhnya salah: 1. Entri tersebut bukan grafik: grafik besar adalah PARAMETER. Jadi masalah hamilton diubah menjadi konstan (sangat besar, tetapi konstan). 2. Entri adalah solusi dari masalah, jadi: jika lebih besar, Anda menawarkan ledakan kombinatorial petunjuk. Entri satu petunjuk memberi bantuan, dua petunjuk ganda, tiga petunjuk akan dekat dengan 4 twices ..., karena Anda menghilangkan solusi yang mungkin. Jadi, ini bukan Hamiltonian, ini adalah solusi dari grafik khusus dan masalahnya adalah APA yang harus dilakukan dengan bagian-bagian dari solusi.

Juan Manuel Dato

Saya pikir argumen Anda menarik karena contoh yang lebih besar "lebih mudah" dalam beberapa hal, tetapi saya pikir jawaban untuk pertanyaan asli pada akhirnya adalah "tidak". Karena grafik terbatas, maka hanya ada banyak petunjuk yang mungkin. Oleh karena itu setiap instance dapat diselesaikan dalam waktu yang konstan (misalnya, menggunakan tabel pencarian). Meskipun instans yang lebih besar (secara intuitif) lebih mudah dalam ilmu komputer (asimptotik), semua instans sama-sama keras (dapat dipecahkan dalam waktu yang konstan).

Tom van der Zanden

@ Tom, saya setuju pertimbangan Anda tentang kompleksitas akan konstan, tetapi masalahnya adalah bagaimana kami menerima petunjuk baru: jika dengan filosofi kami menghitung entri panjang tidak lebih baik daripada entri pendek, maka kami harus mengubah filosofi kami - karena itu adalah fakta: entri panjang menyiratkan masalah yang lebih mudah. Jadi kita tidak bisa bekerja dengan cara itu ... Saya akan merekomendasikan buku saya, tetapi saya tidak punya reputasi ...

Juan Manuel Dato

n \log n

$n\log n$

1

Pertimbangkan sebuah program yang memasukkan apa yang Anda ketahui tentang kata sandi dan kemudian mencoba memecahkannya. Saya pikir ini melakukan apa yang Anda inginkan. Sebagai contoh:

Tidak ada input-> Kekuatan kasar meretakkan semua simbol dan kata dengan panjang berapa pun
Panjang kata sandi -> Brute paksa semua simbol dalam kata yang panjangnya
Simbol yang terkandung -> Menyusutkan daftar simbol untuk diperiksa
...
Simbol yang Terkandung termasuk beberapa kejadian dan panjang -> Hanya menghitung permutasi
Semua simbol dalam urutan yang benar -> pada dasarnya dipecahkan sendiri

Saya harus menambahkan bahwa ini adalah trik, karena masalah yang dinyatakan seperti ini terbalik dengan ukuran input. Anda bisa meninggalkan satu lapisan abstraksi dan mengatakan bahwa ukuran input besar tanpa input (periksa semua simbol dan panjang kata) dan kecil jika Anda memasukkan kata sandi yang benar di awal.

Jadi semuanya tergantung pada seberapa banyak abstraksi yang Anda izinkan.

JalankanOrVeith
sumber

2

b

$b$

0

Sebagai soal fakta, saya punya masalah yang semakin kecil dengan meningkatnya data. Salah satu aplikasi saya mencatat atribut produk tertentu, misalnya keju. Atribut misalnya CheeseType, Merek, Negara, Area, MilkType, dll. Setiap bulan atau lebih, saya mendapatkan daftar keju baru yang masuk ke pasar selama waktu itu, beserta atributnya. Sekarang, atribut-atribut ini diketik dengan tangan oleh sekelompok manusia. Beberapa membuat kesalahan ketik, atau tidak tahu nilai untuk semua atribut.

Ketika Anda melakukan pencarian di basis data saya, saya mencoba memprediksi dari statistik seperti apa rasanya keju, berdasarkan pada atribut-atribut ini. Apa yang terjadi, adalah untuk setiap atribut, saya berakhir dengan rentang nilai; ada yang valid ada yang tidak valid. Menghilangkan atau mengoreksi yang tidak valid ini hanya mungkin jika saya memiliki cukup data. Ini tentang membuat perbedaan antara nilai nyata dan noise, tanpa menghilangkan nilai yang jarang namun valid.

Seperti yang dapat Anda bayangkan, dengan volume rendah, kebisingan terlalu penting untuk memperbaiki keadaan dengan benar. Jika Anda memiliki 5 contoh Cheddar, 1 Brie, 1 Bri, dan 1 Chedar, bagaimana saya tahu mana yang benar dan mana yang salah ketik? Dengan volume yang lebih banyak, kesalahan pengetikan cenderung tetap sangat rendah, tetapi nilai-nilai langka mendapatkan beberapa peningkatan penting, membuat mereka keluar dari kebisingan (didukung oleh pengalaman). Dalam hal ini, saya bisa membayangkan 50000 Cheddar, 3000 Brie, 5 Bri, 15 Chedar, misalnya.

Jadi ya, beberapa masalah akhirnya bisa diselesaikan sendiri, ketika Anda memiliki cukup data.

chris
sumber

1

Ini gagal karena alasan biasa. Input besar mungkin satu di mana orang memberi tahu Anda tentang berbagai jenis keju, daripada satu di mana mereka memberi tahu Anda tentang beberapa jenis keju tetapi beberapa dari mereka salah mengeja itu. Juga, tidak jelas bahwa "lebih mudah" seharusnya ditafsirkan sebagai "memungkinkan kepercayaan yang lebih tinggi pada hasilnya".

David Richerby

Ini adalah masalah kehidupan nyata (saya sudah dua kali melakukannya), yang tidak dapat diselesaikan dengan jumlah data yang rendah. Itu bisa, dan bahkan semakin mudah untuk dipisahkan, nilai-nilai baik dari yang salah, karena volume semakin tinggi. Ini memiliki manfaat menjawab pertanyaan "Apakah ada masalah yang menjadi lebih mudah karena mereka bertambah besar?" Tidak masalah berapa banyak jenis keju yang muncul, pada akhirnya, dengan volume yang cukup, mereka akan memiliki lebih banyak "hit" daripada kesalahan ketik. Ini adalah pertukaran cs .stack, bukan matematika, jadi masalahnya berbeda, dan menyelesaikannya kadang-kadang hanya tentang memiliki kepercayaan yang lebih tinggi pada hasilnya.

chris

Bukankah ini juga semacam premis dari acara TV Numbers ? Atau setidaknya beberapa episode - Saya tahu saya secara khusus mengingat satu adegan di mana orang matematika berkomentar bahwa algoritma yang dia gunakan untuk memecahkan masalah yang ada menjadi lebih efektif dengan dataset yang lebih besar.

Dan Henderson

2

"Mendapat lebih efektif"! = "Menjadi lebih mudah".

David Richerby

-1

Pertimbangkan masalah NP-complete 3-SAT. Jika Anda terus menambah masalah dengan memberikan input formulir x_i = true / false, Anda akhirnya mengubah pemisahan individu menjadi klausa dua variabel, sehingga menciptakan masalah 2-SAT yang dipastikan P, atau Anda akhirnya mendapatkan jawaban benar / salah.

Untuk kasus di mana terdapat redundansi dalam x_i = input benar / salah (input yang sama banyak diberikan, atau input kontradiktif) Anda dapat dengan mudah mengurutkan input dan mengabaikan nilai yang berlebihan, atau melaporkan kesalahan jika nilainya bertentangan.

Bagaimanapun, saya pikir ini merupakan masalah 'realistis' yang semakin mudah dipecahkan ketika jumlah input bertambah. Aspek 'lebih mudah' adalah dalam mengonversi masalah NP-complete ke masalah P. Anda masih dapat memainkan sistem dengan memberikan input yang konyol sehingga penyortiran hanya akan memakan waktu lebih lama dari yang dipaksakan dengan kasar.

Sekarang, skenario yang sangat keren adalah jika kita bersedia menerima T (0) (menggunakan notasi DW dalam jawaban di atas) dapat menjadi tak terbatas. Misalnya, T (0) bisa jadi setara dengan menyelesaikan Masalah Puting Turing. Jika kita dapat menemukan masalah sehingga menambahkan lebih banyak input mengubahnya menjadi masalah yang dapat dipecahkan, kita telah menemukan emas. Perhatikan bahwa tidak cukup untuk mengubahnya menjadi masalah yang dapat dipecahkan secara asimptotik - karena sama buruknya dengan kekerasan yang memaksa masalah tersebut.

v vv cvvcv
sumber

1

Masukan khusus ini menjadi lebih mudah. Namun, ketika Anda mempertimbangkan semua input yang mungkin, 3SAT secara umum menjadi semakin sulit saat Anda menambahkan lebih banyak klausa: input yang sulit adalah yang tanpa klausa "petunjuk" ini. Jika Anda melarang input umum, Anda harus menyatakan dengan tepat input apa yang Anda izinkan.

David Richerby

Pertama: kami sepakat bahwa menambahkan lebih banyak input dapat meningkatkan waktu berjalan. Saya katakan pada dasarnya hal yang sama di atas. Kedua, saya jelas mengatakan kami mengambil 3-SAT yang ada dan hanya menambahkan input dari form x_i = true / false. Saya pikir ini cukup jelas dan saya tidak perlu membuat klarifikasi lebih lanjut. Saya pikir Anda mengambil kesulitan untuk membentuk interpretasi yang paling keliru dari apa yang saya tulis. Tolong, jangan repot-repot.

v vv cvvcv

1

Tidak, serius. Apa masalah komputasi yang Anda selesaikan? Masalah komputasi adalah memutuskan keanggotaan dari serangkaian string (katakanlah seperangkat rumus untuk menghindari gangguan tentang pengkodean). Apa himpunan formula yang Anda klaim yang memutuskan apakah formula panjang di set lebih mudah daripada memutuskan bahwa formula pendek di set? Segera setelah Anda mencoba membuat ini tepat, saya cukup yakin klaim Anda akan berantakan.

David Richerby

Bisakah Anda jelaskan pengertian Anda tentang 'klaim saya'? Segera setelah Anda mencoba untuk membuat ini tepat, saya cukup yakin Anda akan berhenti membuang-buang bandwidth internet.

v vv cvvcv

Saya seorang ilmuwan komputer, bukan pembaca pikiran. Membuat klaim Anda tepat adalah pekerjaan Anda, bukan milik saya.

David Richerby

-1

Pertanyaannya adalah: "mungkinkah ada masalah yang benar-benar menjadi lebih mudah ketika input bertambah besar?" Bagaimana jika input adalah sumber daya yang akan digunakan oleh algoritma untuk bekerja pada suatu pekerjaan. Sudah menjadi rahasia umum bahwa semakin banyak sumber daya semakin baik. Di bawah ini adalah contoh, di mana semakin banyak karyawan, semakin baik.

$n$
$t$ $p$

$n$

3) Output:
Output adalah jalur antara tugas yang harus diambil oleh karyawan. Setiap jalur dikaitkan dengan jumlah karyawan yang mengambilnya. Sebagai contoh:

$n1$
$n2$
$n3$
$n4$
$n5$

4) Kemungkinan solusi:
Salah satu solusi yang mungkin adalah pertama menghitung jalur terpendek ke node terdekat dari A. Ini akan menjadi jalur maju. Kemudian secara rekursif menghitung jalur maju untuk setiap tugas yang dikunjungi. Hasilnya adalah pohon. Sebagai contoh:

          SEBUAH
      SM
    DE

$n$ $n1$ $n2$ $n2 \neq 0$

$n=\infty$ $n = 1$

$n$

yemelitc
sumber

6

Terima kasih telah berbagi pemikiran Anda. Biasanya dalam ilmu komputer suatu algoritma dipahami untuk menerima urutan bit sebagai inputnya, dan output urutan bit lain. Dengan pemahaman standar itu, saya tidak melihat bagaimana jawaban ini masuk akal. Jika Anda memiliki gagasan algoritma yang berbeda dalam pikiran, saya pikir itu akan membantu jika Anda mengedit pertanyaan untuk menggambarkan apa yang Anda maksudkan dengan algoritma (karena sepertinya Anda tidak menggunakan istilah dengan cara yang sesuai dengan penggunaan standar istilah, seperti yang saya mengerti).

DW

Input bisa berupa angka (jumlah sumber daya). Ini akan memengaruhi jumlah komputasi ekstra yang harus dilalui algoritma. Saya akan mengedit jawaban untuk memberikan contoh yang lebih konkret.

yemelitc

Terima kasih atas hasil edit Anda - yang membuatnya lebih jelas. Saya sekarang melihat bahwa Anda tidak mengacaukan biaya komputasi solusi dengan biaya pelaksanaannya seperti yang saya pikirkan. Tapi sekarang kita dalam situasi yang biasa. Pertama, setidaknya diperlukan waktu linear untuk membaca input. Kedua, contoh-contoh sulit bukanlah yang Anda berikan pohon kecil dan trilyun orang, tetapi di mana Anda memberi pohon besar dan relatif sedikit orang. (Misalnya, jika Anda mengizinkan saya sejuta bit, saya akan memilih pohon dengan sekitar seribu simpul dan memberi Anda lima orang, bukan pohon dengan lima simpul dan seribu orang.)

David Richerby

Saya setuju. Sepertinya kita semua akhirnya cukup kritis tentang hal itu, tidak seperti apa yang membuat kita tergoda! Tapi mudah-mudahan Anda mendapatkan ide saya tentang 'input sebagai sumber daya': tidak peduli seberapa besar pekerjaannya, semakin banyak orang semakin baik. Masih dalam pengertian asimptotik Anda pasti benar, saya hanya harus menyalahkannya pada bilangan bulat non-negatif.

yemelitc

Apakah ada masalah yang semakin mudah karena ukurannya bertambah?

Jawaban: