Apakah ada metode untuk analisis runtime algoritma otomatis?

10

Saya bertanya-tanya, apakah ada metode untuk analisis runtime otomatis yang berfungsi setidaknya pada subset algoritma yang relevan (algoritma yang dapat dianalisis)?

Saya googled "Analisis algoritma otomatis" yang memberi saya ini tetapi terlalu matematika. Saya hanya ingin contoh sederhana dalam psuedocode yang bisa saya mengerti. Mungkin terlalu spesifik, tapi saya pikir itu layak dicoba.

algorithms algorithm-analysis reference-request runtime-analysis Nathvi
sumber
Saya gagal melihat bagaimana tekanan antara "apa saja" dan "suatu" mengklarifikasi apa yang sebenarnya Anda cari. Jika beberapa prosedur pengambilan keputusan terikat pada algoritma B tertentu, maka tidak ada input nyata dan jawabannya selalu sama. Saya pikir apa yang ingin Anda tanyakan adalah jika 'ada algoritma dalam beberapa kelas algoritma' di mana kelas terikat / dikenal. (sunting: ini telah menunjukkan komentar mhum saya juga).
Nicholas Mancuso
2
Ambiguitas dalam penggunaan "an" dan "apa pun" adalah alasan mengapa quantifiers ditemukan.
Nate Eldredge
2
Saya mengedit pertanyaan untuk fokus pada bagian yang relevan. Perhatikan bagaimana saya menggunakan nol matematika untuk mengungkapkan masalah secara akurat (sejauh yang Anda tentukan pertanyaan Anda sampai sekarang) dan secara ringkas. Sekarang, pertanyaannya masih salah: tentu saja ada algoritma seperti itu. Sebagai contoh, ada algoritma sederhana yang menganalisis semua algoritma dari kelas algoritma (sangat relevan) yang berjalan dalam waktu . Oleh karena itu Anda jelas perlu menempatkan beberapa pembatasan pada set input. (Perhatikan bahwa mungkin tidak ada "contoh sederhana dalam psuedocode yang dapat saya mengerti".)Θ(nlog⁡n)
Raphael

Jawaban:

12

Alat COSTA melakukan hal ini, meskipun gagal dalam banyak kasus, seperti yang dapat Anda bayangkan, karena masalah komputabilitas . Ada banyak makalah tentang ini; Analisis Biaya Java Bytecode oleh E. Albert, P. Arenas, S. Genaim, G. Puebla, D. Zanardini adalah titik awal yang baik.

Pendekatan yang diambil adalah untuk menyimpulkan pengulangan run-time dari kode Javabyte, mengubahnya menjadi bentuk tertutup. Alat ini juga menghitung batas penggunaan ruang.

Dave Clarke
sumber
8
@Nathvi Saya bisa mengerti Anda kesal dengan beberapa komentar, yang saya setuju tidak benar-benar diperlukan, tetapi Anda juga harus berhati-hati untuk tidak menggunakan istilah "omong kosong pedantic" untuk karya ilmuwan yang sangat terkenal (dan kebetulan jawaban saya). Anda berhak untuk tidak menyukai matematika, tetapi Anda tidak akan berhasil tanpa itu, dan kata-kata menghina yang tidak ada gunanya tidak membantu siapa pun.
babou
12

Tidak ada algoritma yang dapat memutuskan apakah algoritma yang diberikan pernah berhenti atau tidak, jadi khususnya tidak ada algoritma yang dapat menganalisis kompleksitas algoritma yang diberikan dengan ketat.

Yuval Filmus
sumber
2
Pertanyaan saya bukan tentang algoritma yang dimasukkan secara sewenang-wenang, yang jika ya, maka jawaban Anda akan benar, karena masalah penghentian. Anda akan benar jika pertanyaan saya diucapkan: "Apakah ada algoritma A yang mencakup semua algoritma B, dan kemudian menampilkan kompleksitas waktu dari algoritma B?"
Nathvi
6
Jika algoritma B diperbaiki, maka pastikan ada algoritma A. Cukup untuk memiliki algoritma yang tidak melakukan apa pun selain mencetak "O (n)" atau ukuran kompleksitas apa pun yang sesuai dengan B. Jika hanya ada satu input yang mungkin untuk algoritma A, maka kita hanya perlu satu output.
mhum
5
@Nathvi juga tidak jelas bagi saya - saya juga mengerti pertanyaannya sebagai "apakah ada algoritma untuk menemukan kompleksitas dari algoritma lain", dan saya masih tidak mengerti pertanyaan Anda yang sebenarnya . Jika Anda menghitung penghitungan suara, tampaknya> 2 orang menafsirkannya seperti itu. Jika bingung, sebaiknya Anda mengedit pertanyaan Anda, jika tidak hanya orang yang membaca percakapan ini (daripada semua orang yang membaca pertanyaan) yang akan memahami apa yang Anda tanyakan dan memberikan jawaban yang baik. Sepertinya Anda merasa respons DW bermusuhan - FWIW, saya tidak berpikir itu dimaksudkan untuk menjadi ..
jkff
6
@ignis Jawabannya mungkin tidak lengkap tetapi kalimat yang ditulis Yuval benar sekali. Dan masalah penghentian bukanlah beberapa kasus sampingan yang eksotis: itu adalah inti dari perhitungan.
David Richerby
3
@nikie Itu tidak membantu sejauh pertanyaan ini berlangsung; Batas runtime tidak dapat ditentukan bahkan pada set semua algoritma yang selalu berakhir.
Raphael
9

Saya tahu satu pendekatan untuk analisis kasus rata-rata (semi-) otomatis, yaitu MaLiJAn ¹. Ini sangat mirip dengan jenis analisis yang digunakan Knuth di TAoCP. Gagasan intinya adalah untuk

  • memodelkan program (aliran) sebagai Markov Chain,
  • melatih probabilitas transisinya untuk beberapa ukuran input tetap n dengan menghitung serangkaian program yang berjalan (yang menghasilkan penduga kemungkinan maksimum ),
  • ekstrapolasi ke fungsi probabilitas dalam n dan
  • gunakan aljabar komputer untuk menurunkan biaya rata-rata (wrt fungsi-fungsi ini).

Perhatikan bahwa hanya pengukuran biaya tambahan (mis. Perbandingan, "waktu") yang berfungsi dan hanya nilai yang diharapkan yang akurat (dengan asumsi fungsi probabilitas sempurna), momen yang lebih tinggi tidak dapat diturunkan.

Semua langkah kecuali ekstrapolasi sangat ketat [2] dan metode ini telah ditunjukkan untuk mereproduksi hasil yang terkenal dengan presisi tinggi - tentu saja, memberikan input sampel acak yang sesuai. Meskipun tidak ada bukti atau bahkan jaminan perkiraan pada hasil (langkah ekstrapolasi, sejauh ini, murni heuristik) hasil yang diperoleh dengan alat berfungsi dengan baik untuk bereksperimen dengan algoritma yang sulit dianalisis dan merumuskan hipotesis [3,4].

  1. Pengungkapan penuh: Saya adalah anggota kelompok riset ini dan telah terlibat dalam pengembangan alat ini.
  2. Analisis Kemungkinan maksimum Algoritma dan Struktur Data oleh U. Laube dan M. Nebel (2010) [ pracetak ]
  3. Rekayasa Quicksort Dual Pivot Java 7 Menggunakan MaLiJAn oleh S. Wild et al (2012) [ preprint ]
  4. Analisis Kemungkinan Maksimum dari Metode Ford – Fulkerson pada Grafik Khusus oleh U. Laube und M. Nebel (2015) [ pracetak ]
Raphael
sumber
Apakah teknik-teknik ini datang dengan estimasi ketepatan analisis kasus rata-rata?
Martin Berger
@ MartinBerger Sayangnya, tidak. Kami punya beberapa ide tentang itu tetapi belum ada yang diperkuat apalagi diimplementasikan. Perhatikan bahwa mudah untuk mengelabui metode apa pun yang hanya memeriksa ukuran input yang terbatas, sehingga secara umum ada sedikit harapan. Dengan asumsi pada fungsi runtime dan / atau kumpulan data, sesuatu mungkin terjadi. Alat setidaknya harus bisa mengatakan "butuh lebih banyak data".
Raphael
Itu menarik. Saya harap Anda berkeliling melakukan pekerjaan tambahan ini.
Martin Berger
8

Tentu saja, seperti dicatat oleh Yuval Filmus, orang seharusnya tidak mengharapkan solusi umum untuk masalah seperti itu. Tetapi seperti biasanya, solusi dapat ditemukan untuk himpunan bagian yang menarik dari kasus umum.

Saya sama sekali tidak ahli, atau bahkan berpengetahuan luas di bidang ini, oleh karena saya tahu beberapa pekerjaan semacam itu. Ini menyangkut analisis kompleksitas rata-rata otomatis, dan pekerjaan itu dilakukan oleh Philippe Flajolet dan rekan-rekannya.

λkamu´ω

Satu makalah yang saya temukan di web adalah makalah tahun 1990: Analisis algoritme kasus rata-rata otomatis oleh Philippe Flajolet, Paul Zimmermann, dan Bruno Salvy .

Saya berharap bahwa makalah-makalah selanjutnya akan memperpanjang pekerjaan ini, tetapi saya tidak benar-benar tahu. Karya itu cukup banyak dikutip, dan mencari di web untuk itu harus menghasilkan lebih banyak karya terbaru tentang topik yang sama.

Sekarang, saya takut bahwa karya Flajolet dan rekan-rekannya sangat matematis, dan saya tidak berharap banyak membaca dengan mudah.

babou
sumber