Встроенная функция PHP (функция isAnagramOfPalindrome)

Я занимаюсь поиском в Интернете за последние 2 часа, и я не могу найти список встроенных функций времени и пространства php. У меня проблема isAnagramOfPalindrome решить со следующей максимально допустимой сложностью:

expected worst-case time complexity is O(N)

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

где N - длина входной строки. Вот мое самое простое решение, но я не знаю, находится ли он в пределах сложности.

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

У кого-нибудь есть идея, где найти такую информацию?

ИЗМЕНИТЬ

Я выяснил, что array_filter имеет сложность O (N), а count имеет сложность O (1). Теперь мне нужно найти информацию о count_chars, но полный список будет очень удобен для будущих эмблем.

РЕДАКТИРОВАТЬ 2

После некоторых исследований по сложности пространства и времени в целом я обнаружил, что этот код имеет сложность времени O (N) и сложность пространства O (1), потому что:

count_chars будет цикл N раз (полная длина входной строки, что дает ей начальную сложность O (N)). Это генерирует массив с ограниченным максимальным количеством полей (26 точно, количество разных символов), а затем он применяет фильтр к этому массиву, что означает, что фильтр будет петлиться не более 26 раз. При нажатии на входную длину до бесконечности этот цикл незначителен и рассматривается как константа. Count также относится к этому сгенерированному постоянному массиву, и, кроме того, он незначителен, поскольку сложность функции count равна O (1). Следовательно, временная сложность алгоритма O (N).

Это то же самое с пространственной сложностью. При вычислении сложности пространства мы не учитываем входные данные, а только объекты, сгенерированные в процессе. Эти объекты представляют собой массив из 26 элементов и переменную count, и оба они рассматриваются как константы, потому что их размер не может увеличиться по сравнению с этой точкой, независимо от того, насколько велик вход. Таким образом, мы можем сказать, что алгоритм имеет пространственную сложность O (1).

В любом случае этот список будет по-прежнему ценным, поэтому нам не нужно заглядывать в исходный код php.:)

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; }

$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));

Ответ 1