Trova automaticamente la notazione di Landau (notazione Big O o Theta) di un algoritmo?

I was wondering how they do that... How would you do it?

Immagino che in realtà stimino le misure di Big O ... eseguendo il programma per diverse dimensioni dei problemi, misurando il tempo e l'utilizzo dello spazio e adattando le curve ai risultati.

Il problema con questo approccio è che può sbagliare se le funzioni di costo cambiano forma quando N diventa grande; per esempio. 1000 N + N^1.5 .

Is there another way besides Lexical Analysis or parsing of the code?

L'analisi lessicale e l'analisi non sono sufficienti. È inoltre necessario fare alcuni ragionamenti sul comportamento dell'algoritmo. E farlo automaticamente per un algoritmo precedentemente sconosciuto è difficile.

Non possono farlo senza analizzare il codice.

Sotto esempi con "inflazione / deflazione" artificiale di complessità dimostra che la semplice misurazione del runtime del programma non è sufficiente per stimare in modo affidabile 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);
}

La stima del runtime per quanto sopra potrebbe essere accettabile dando stime false - tempo costante per valori di n dove c'è una soluzione precalcolata e un tempo cubico per i valori in cui unfair slow-down interviene - invece di un tempo quadratico "giusto" .

Penso che questo non sia possibile.

Se si eseguono alcuni test con un numero fisso di diverse dimensioni di input, è possibile calcolare facilmente un polinomio, che approssimerà i tempi di esecuzione che si sono misurati molto bene. Quindi si finisce con un polinomio per ogni possibile programma, che vorrebbe dire P = NP (yeah!;)).

Se provi a farlo con la manipolazione simbolica, finisci con halting problem . Dal momento che non puoi decidere se il tuo programma si fermerà mai, non puoi decidere quale sarà la complessità del runtime.

Potrebbero tuttavia esserci casi molto speciali, in cui è possibile il metodo successivo. Ma questi casi sono forse così piccoli, che è discutibile che uno sforzo venga mai pagato.

Come potrei farlo? Il modo in cui risolvo quasi tutti i problemi non voglio sedermi e risolvere . Io simulo.

Per molti problemi, potrebbe essere sufficiente eseguire l'algoritmo molte volte utilizzando una varietà di dimensioni e quindi adattare una curva di regressione a tali risultati. Ciò potrebbe identificare rapidamente alcuni particolari costi generali "fissi" dell'algoritmo (l'intercetta della curva) e il modo in cui viene ridimensionato all'aumentare della dimensione del problema.

Saranno necessari alcuni ritocchi per catturare soluzioni particolarmente complicate, ma soprattutto se stai solo cercando una stima del parco giochi, dovresti essere in grado di ottenerla in questo modo e vedere come la tua stima differisce dai tuoi risultati effettivi e decidere se è un'approssimazione accettabile.

Il più grande punto debole nella mia mente con questo metodo è che se il tuo algoritmo ridimensiona veramente in modo insufficiente, quel passo iniziale "eseguilo un sacco di volte" diventerà brutto. Ma francamente, è così, che da solo dovrebbe essere un indicatore che potresti voler fare un passo indietro e riconsiderare le cose.

La mia intuizione è che una soluzione generale a questo problema è impossibile; asserendo, così come, i fatti a priori sul runtime degli algoritmi senza eseguirli (si allude all'analisi lessicale). Detto questo, è possibile per qualche algoritmo euristico per una (probabilmente grande) classe di algoritmi (dato che lo facciamo sempre), ma un algoritmo generale per farlo sarebbe equivalente a risolvere il Entscheidungsproblem che è ben noto non essere possibile (cfr Church, Turing, et al.). Sono sicuro al 99,9% di questo ora che ci penso ...