Apakah ada algoritma untuk optimasi kompleksitas waktu / ruang algoritma?

9

Pada 1950-an sejumlah metode untuk meminimalkan sirkuit untuk fungsi Boolean telah ditemukan. Apakah ada perluasan dari metode tersebut atau yang serupa untuk mengoptimalkan kompleksitas waktu atau ruang dari algoritma?

Misalnya implementasi bubble sort sebagai input untuk algoritma seperti itu akan menghasilkan implementasi algoritma sorting dengan kompleksitas waktu yang lebih dekat ke .HAI(ncatatan⁡n)

algorithms turing-machines time-complexity optimization space-complexity Pengoptimal
sumber
1
Pergi!! Kami profesional CS mencari nafkah dari mengajar algoritma yang canggih, saran Anda akan meninggalkan kami tanpa pekerjaan!
vonbrand
Nah ... lalu apa yang Anda harapkan dari AI?
Pengoptimal
Bubble sort bukanlah fungsi Boolean. Lebih buruk lagi, tidak semua algoritma penyortiran setara! Misalnya, ada yang tidak stabil.
Yuval Filmus
Anda benar, tetapi bubble sort dan "good sort" hanyalah contoh dari apa yang saya lihat sebagai input dan output, jangan berkonsentrasi pada detail.
Pengoptimal
@YuvalFilmus pasti mengembalikan array yang diurutkan tidak lebih mudah daripada mengembalikan benar atau salah
vonbrand

Jawaban:

11

Lihat teorema speedup Blum (ya, artikel ini kurang informatif; lihat buku tentang teori kompleksitas). Pada dasarnya dikatakan bahwa ada program yang ada program melakukan pekerjaan yang sama yang lebih cepat dengan margin yang ditentukan untuk hampir semua data input.

Dengan teorema Rice , tidak mungkin untuk mengetahui apakah dua program yang diberikan melakukan pekerjaan yang sama.

Ya, untuk beberapa gagasan yang sangat terbatas tentang "program", diberikan contoh orang dapat membangun program "terbaik" untuk pekerjaan itu. Bahkan kelas-kelas penting. Tapi sangat jauh dari apa pun yang mampu mengekspresikan gelembung.

vonbrand
sumber