Eu tenho pesquisado no Google nas últimas 2 horas, e não consigo encontrar uma lista do php construído em funções de tempo e complexidade do espaço. Eu tenho oisAnagramOfPalindrome problema a ser resolvido com a seguinte complexidade máxima permitida:

expected worst-case time complexity is O(N)

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

onde N é o comprimento da string de entrada. Aqui está minha solução mais simples, mas não sei se ela está dentro dos limites de complexidade.

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']);

Alguém tem uma idéia de onde encontrar esse tipo de informação?

EDITAR

Eu descobri quearray_filter tem complexidade O (N) ecount tem complexidade O (1). Agora preciso encontrar informações sobrecount_chars, mas uma lista completa seria muito conveniente para futuros emblemas.

EDIT 2

Após algumas pesquisas sobre complexidade de espaço e tempo em geral, descobri que esse código possui complexidade de tempo O (N) e complexidade de espaço O (1) porque:

ocount_chars fará um loop N vezes (comprimento total da sequência de entrada, proporcionando uma complexidade inicial de O (N)). Isso está gerando uma matriz com número máximo limitado de campos (26 precisamente, o número de caracteres diferentes) e, em seguida, aplicando um filtro nessa matriz, o que significa que o filtro fará um loop 26 vezes no máximo. Ao empurrar o comprimento da entrada para o infinito, esse loop é insignificante e é visto como uma constante. Count também se aplica a esse array constante gerado e, além disso, é insignificante porque ocount a complexidade da função é O (1). Portanto, a complexidade do tempo do algoritmo é O (N).

É o mesmo com a complexidade do espaço. Ao calcular a complexidade do espaço, não contamos a entrada, apenas os objetos gerados no processo. Esses objetos são a matriz de 26 elementos e a variável count, e ambos são tratados como constantes porque seu tamanho não pode aumentar nesse ponto, não importa o tamanho da entrada. Então, podemos dizer que o algoritmo tem uma complexidade espacial de O (1).

De qualquer forma, essa lista ainda seria valiosa, portanto não precisamos procurar dentro do código-fonte php. :)