PHP integrato nella complessità delle funzioni (funzione AnagramOfPalindrome)

Question

Ho cercato su Google nelle ultime 2 ore e non riesco a trovare un elenco di funzioni integrate di php in termini di tempo e spazio. Ho il problema isAnagramOfPalindrome da risolvere con la seguente complessità massima consentita:

expected worst-case time complexity is O(N) 

expected worst-case space complexity is O(1) (not counting the storage required for input arguments). 

dove N è la lunghezza della stringa di input. Ecco la mia soluzione più semplice, ma non so se rientra nei limiti di complessità.

class Solution { 

    // Function to determine if the input string can make a palindrome by rearranging it 
    static public function isAnagramOfPalindrome($S) { 

     // here I am counting how many characters have odd number of occurrences 
     $odds = count(array_filter(count_chars($S, 1), function($var) { 
      return($var & 1); 
     })); 
     // If the string length is odd, then a palindrome would have 1 character with odd number occurrences 
     // If the string length is even, all characters should have even number of occurrences 
     return (int)($odds == (strlen($S) & 1)); 
    } 
} 

echo Solution :: isAnagramOfPalindrome($_POST['input']); 

Qualcuno ha un'idea su dove trovare questo tipo di informazioni?

EDIT

ho scoperto che array_filter ha O (N) complessità e count ha O (1) complessità. Ora ho bisogno di trovare informazioni su count_chars, ma un elenco completo sarebbe molto conveniente per i futuri problemi.

EDIT 2

Dopo qualche ricerca su spazio e tempo della complessità, in generale, ho scoperto che questo codice ha O (n) la complessità e O (1) spazio complessità perché:

Il count_chars eseguirà il ciclo N volte (tutta la lunghezza della stringa di input, dandogli una complessità iniziale di O (N)). Questo sta generando un array con un numero massimo limitato di campi (26 precisamente, il numero di caratteri diversi), e quindi applica un filtro su questo array, il che significa che il filtro eseguirà il ciclo 26 volte al massimo. Quando si spinge la lunghezza dell'input verso l'infinito, questo loop è insignificante e viene visto come una costante. Il conteggio si applica anche a questo array costante generato e inoltre non è significativo poiché la complessità della funzione count è O (1). Quindi, la complessità temporale dell'algoritmo è O (N).

È lo stesso con la complessità dello spazio. Quando calcoliamo la complessità dello spazio, non contiamo l'input, ma solo gli oggetti generati nel processo. Questi oggetti sono l'array a 26 elementi e la variabile count, ed entrambi sono trattati come costanti perché la loro dimensione non può aumentare oltre questo punto, non importa quanto grande sia l'input. Quindi possiamo dire che l'algoritmo ha una complessità spaziale di O (1).

In ogni caso, tale elenco sarebbe ancora prezioso quindi non dobbiamo guardare all'interno del codice sorgente php. :)

Answer 1

Un motivo probabile per non includere questa informazione è che è probabile che cambi per versione, come miglioramenti sono apportati/ottimizzazioni per un caso generale.

PHP è costruito su C, alcune delle funzioni sono semplicemente wrapper intorno alle controparti C, ad esempio hypot una ricerca su Google, uno sguardo al man hypot, nella documentazione per lui la matematica lib http://www.gnu.org/software/libc/manual/html_node/Exponents-and-Logarithms.html#Exponents-and-Logarithms

La fonte realtà non fornisce migliori informazioni https://github.com/lattera/glibc/blob/a2f34833b1042d5d8eeb263b4cf4caaea138c4ad/math/w_hypot.c (non ufficiale, solo facile da collegare a)

Per non parlare, questo è solo glibc, Windows avrà un'implementazione diversa.Quindi ci potrebbe anche essere un grande O diverso per ogni sistema operativo che PHP è compilato su

Un altro motivo potrebbe essere dovuto al fatto sarebbe confondere la maggior parte degli sviluppatori. maggior parte degli sviluppatori che conosco sarebbe semplicemente scegliere una funzione con il "migliore" grande O

un doesnt massima media sempre la sua più lenta

http://www.sorting-algorithms.com/

ha un buon puntello visiva di quello che accade con alcune funzioni , ad esempio bubble sort è un tipo "lento", ma è uno dei più veloci per dati quasi ordinati. L'ordinamento rapido è quello che molti useranno, che in realtà è molto lento per dati quasi ordinati. Big O è il caso peggiore - PHP può decidere tra una release che dovrebbe ottimizzare per una determinata condizione e che cambierà la grande O della funzione e non esiste un modo semplice per documentarla.

V'è una lista parziale qui (che immagino che avete visto)

List of Big-O for PHP functions

che fa elencare alcune delle funzioni più comuni PHP.

Per questo particolare esempio ....

È abbastanza facile da risolvere senza utilizzare il costruito nel funzioni.

codice di esempio

function isPalAnagram($string) { 
    $string = str_replace(" ", "", $string); 
    $len = strlen($string); 
    $oddCount = $len & 1; 
    $string = str_split($string); 
    while ($len > 0 && $oddCount >= 0) { 
    $current = reset($string); 
    $replace_count = 0; 
    foreach($string as $key => &$char) { 
     if ($char === $current){ 
     unset($string[$key]); 
     $len--; 
     $replace_count++; 
     continue; 
     } 
    } 
    $oddCount -= ($replace_count & 1); 
    } 

    return ($len - $oddCount) === 0; 

} 

Usando il fatto che non ci possono essere più di 1 conteggio strano, è possibile tornare presto dalla matrice.

I think mine è anche O (N) time perché il suo caso peggiore è O (N) per quanto posso dire.

prova

$a = microtime(true); 
for($i=1; $i<100000; $i++) { 
    testMethod("the quick brown fox jumped over the lazy dog"); 
    testMethod("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"); 
    testMethod("testest"); 
} 
printf("Took %s seconds, %s memory", microtime(true) - $a, memory_get_peak_usage(true)); 

test eseguiti usando veramente vecchio hardware Il mio modo

Took 64.125452041626 seconds, 262144 memory 

Il tuo modo

Took 112.96145009995 seconds, 262144 memory 

Sono abbastanza sicuro che il mio modo non è il modo più rapido o.

In realtà non vedo molte informazioni né per le lingue diverse da PHP (Java per esempio).

Conosco un sacco di questo post sta speculando sul perché la sua non c'è e theres non molto attingendo da fonti credibili, spero che la sua una parte spiegato perché O grande isnt elencata nella pagina di documentazione anche se