Я занимаюсь поиском в Интернете за последние 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 , но полный список будет очень удобен для будущих проблем.
EDIT 2
После некоторых исследований по пространственной и временной сложности в целом я обнаружил, что этот код имеет сложность O (N) и сложность пространства O (1), потому что:
count_chars будет цикл N раз (полная длина входной строки, что дает ей начальную сложность O (N)). Это генерирует массив с ограниченным максимальным количеством полей (26 точно, количество разных символов), а затем он применяет фильтр к этому массиву, что означает, что фильтр будет петлиться не более 26 раз. При нажатии на входную длину до бесконечности этот цикл незначителен и рассматривается как константа. Count также применяется к этому сгенерированному постоянному массиву, и, кроме того, он незначителен, поскольку сложность функции count – O (1). Следовательно, временная сложность алгоритма O (N).
То же самое происходит с пространственной сложностью. При вычислении сложности пространства мы не учитываем входные данные, а только объекты, сгенерированные в процессе. Эти объекты представляют собой массив из 26 элементов и переменную count, и оба они рассматриваются как константы, потому что их размер не может увеличиться по сравнению с этой точкой, независимо от того, насколько велик вход. Таким образом, мы можем сказать, что алгоритм имеет пространственную сложность O (1).
В любом случае, этот список будет по-прежнему ценным, поэтому нам не нужно заглядывать в исходный код php. 🙂
Вероятная причина не включать эту информацию заключается в том, что она, вероятно, будет изменена в расчете на выпуск , поскольку улучшения сделаны / оптимизированы для общего случая.
PHP построен на C. Некоторые из функций – это просто обертки вокруг c-аналогов, например, hypot google search, посмотрите на man hypot , в документах для него math lib http://www.gnu.org/software/ Libc / ручной / html_node / Экспоненты-и-Logarithms.html # Экспоненты и-Логарифмы
Источник фактически не дает никакой информации https://github.com/lattera/glibc/blob/a2f34833b1042d5d8eeb263b4cf4caaea138c4ad/math/w_hypot.c (не является официальным, просто с ним можно связаться)
Не говоря уже о том, что это только glibc, Windows будет иметь другую реализацию. Таким образом, МОЖНО даже быть другим большим O для ОС, который PHP компилируется на
Другая причина может заключаться в том, что это смущает большинство разработчиков . Большинство разработчиков, которых я знаю, просто выбирают функцию с «лучшим» большим O
максимум не всегда означает, что он медленнее
http://www.sorting-algorithms.com/
Имеет хорошую визуальную подсказку о том, что происходит с некоторыми функциями, т. Е. Сортировка пузыря – это «медленный» вид, но одна из самых быстрых для почти отсортированных данных. Быстрая сортировка – это то, что многие будут использовать, что на самом деле очень медленно для почти отсортированных данных. Big O – худший случай – PHP может решить между выпуском, который они должны оптимизировать для определенного условия, и это изменит большую функцию O, и нет простого способа документировать это.
Здесь есть частичный список (который, я думаю, вы видели)
Список функций Big-O для PHP
Который перечисляет некоторые из наиболее распространенных функций 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; }с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; }
Используя тот факт, что не может быть больше 1 нечетного счета, вы можете вернуться раньше из массива.
Я думаю, что мое также O (N), потому что его худший случай – O (N), насколько я могу судить.
Контрольная работа
$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));
Тесты выполняются с использованием действительно старого оборудования. Мой путь
Took 64.125452041626 seconds, 262144 memory
Твой путь
Took 112.96145009995 seconds, 262144 memory
Я совершенно уверен, что мой путь не самый быстрый путь.
Я на самом деле не вижу много информации ни для языков, кроме PHP (например, Java).
Я знаю, что многие из этих сообщений размышляют о том, почему его не существует, и theres не много рисуют из достоверных источников, я надеюсь, что его частично объяснил, почему большой O не указан на странице документации, хотя