Programmaticaly menemukan notasi Landau (notasi Big O atau Theta) dari suatu algoritma?

Saya sudah terbiasa mencari notasi Landau (Big O, Theta ...) dengan tangan saya untuk memastikan mereka seoptimal mungkin, tetapi ketika fungsinya semakin besar dan kompleks, butuh waktu. terlalu banyak waktu untuk melakukannya dengan tangan. itu juga rentan terhadap kesalahan manusia.

Saya menghabiskan beberapa waktu pada Codility (latihan coding / algo), dan memperhatikan bahwa mereka akan memberi Anda notasi Landau untuk solusi yang Anda kirimkan (baik dalam penggunaan Waktu dan Memori).

Saya bertanya-tanya bagaimana mereka melakukan itu ... Bagaimana Anda melakukannya?

Apakah ada cara lain selain Analisis Leksikal atau penguraian kode?

Pertanyaan ini terutama menyangkut PHP dan atau JavaScript, tetapi saya terbuka untuk bahasa dan teori apa pun.

Saya bertanya-tanya bagaimana mereka melakukan itu ... Bagaimana Anda melakukannya?

Saya membayangkan bahwa mereka benar-benar memperkirakan ukuran O Besar ... dengan menjalankan program untuk ukuran masalah yang berbeda, mengukur waktu dan penggunaan ruang, dan menyesuaikan kurva dengan hasilnya.

Masalah dengan pendekatan ini adalah bahwa ia bisa salah jika fungsi biaya berubah bentuk ketika N menjadi besar; mis 1000 N + N^1.5.

Apakah ada cara lain selain Analisis Leksikal atau penguraian kode?

Analisis leksikal dan penguraian tidak cukup. Anda juga perlu melakukan beberapa alasan tentang perilaku algoritma. Dan melakukan itu secara otomatis untuk algoritma yang sebelumnya tidak dikenal itu sulit.

Mereka tidak bisa tanpa menganalisis kode.

Contoh di bawah ini dengan kompleksitas "inflasi / deflasi" buatan membuktikan bahwa hanya mengukur runtime program tidak cukup untuk secara andal memperkirakan Big-O

void lets_trick_runtime(int n) {
   if (n == 10 || n == 25 || n == 118) {
      // unfair speed-up
      do_precalculated_solution_in_constant_time(n);
      return;
   }
   if (n == 11 || n == 26 || n == 119) {
      // unfair slow-down
      do_some_fake_processing_in_n_cube_time(n);
      return;
   }
   // fair solution
   do_general_solution_in_quadratic_time(n);
}

Estimasi Runtime untuk di atas akan lebih mudah untuk memberikan estimasi palsu - waktu konstan untuk nilai di nmana ada solusi pra-dihitung dan waktu kubik untuk nilai-nilai di mana unfair slow-downtendangan masuk - alih-alih waktu kuadratik "adil".

Saya pikir ini tidak mungkin.

Jika Anda menjalankan beberapa tes dengan sejumlah ukuran input yang berbeda, Anda dapat dengan mudah menghitung polinomial, yang akan memperkirakan runtime yang Anda ukur dengan sangat baik. Jadi Anda berakhir dengan polinomial untuk setiap program yang mungkin, yang artinya P = NP(yeah!;)).

Jika Anda mencoba melakukannya dengan manipulasi simbolis, Anda berakhir di halting problem. Karena Anda tidak dapat memutuskan apakah program Anda akan pernah berhenti, Anda tidak dapat memutuskan kompleksitas runtime apa yang akan dimilikinya.

Namun mungkin ada kasus yang sangat khusus, di mana metode selanjutnya mungkin. Tetapi kasus-kasus ini mungkin sekecil itu, sehingga patut dipertanyakan jika upaya pernah dibayar.

Bagaimana saya melakukannya? Cara saya memecahkan hampir semua masalah yang tidak ingin saya duduki dan pecahkan . Saya mensimulasikan.

Untuk banyak masalah, mungkin cukup menjalankan algoritma Anda berkali-kali menggunakan berbagai ukuran, dan kemudian menyesuaikan kurva regresi dengan hasil tersebut. Itu akan dengan cepat mengidentifikasi beberapa biaya overhead "tetap" tertentu dari algoritme Anda (intersepsi kurva) dan bagaimana skala itu seiring dengan meningkatnya ukuran masalah Anda.

Beberapa bermain-main akan diperlukan untuk menangkap solusi yang sangat rumit, tetapi terutama jika Anda hanya mencari perkiraan ball-park, Anda harus bisa mendapatkannya dengan cara itu, dan melihat bagaimana perkiraan Anda berbeda dari hasil aktual Anda dan memutuskan apakah itu perkiraan yang dapat diterima.

Kelemahan terbesar dalam pikiran saya dengan metode ini adalah bahwa jika algoritma Anda berskala sangat buruk, langkah awal "jalankan sejumlah kali" akan menjadi jelek. Tapi sejujurnya, itulah masalahnya, itu saja yang seharusnya menjadi indikator bahwa Anda mungkin ingin mundur dan mempertimbangkan kembali hal-hal.

Intuisi saya adalah bahwa solusi umum untuk masalah ini tidak mungkin; menyatakan, sebagaimana adanya, fakta apriori tentang runtime algoritma tanpa menjalankannya (Anda menyinggung analisis leksikal). Yang mengatakan, adalah mungkin untuk beberapa algoritma heuristik untuk kelas (mungkin besar) algoritma (karena kita melakukannya sepanjang waktu), tetapi algoritma umum untuk melakukan ini akan setara dengan menyelesaikan Entscheidungsproblem yang dikenal tidak menjadi mungkin (lih. Gereja, Turing, dkk.). Saya ~ 99,9% yakin akan hal ini sekarang karena saya memikirkannya ...