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

Question

Я занимаюсь поиском в Интернете за последние 2 часа, и я не могу найти список встроенных функций времени и пространства. У меня есть 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. :)

Answer 1

Возможная причина не включать эту информацию - это , которая может быть изменена в расчете на выпуск, так как сделаны улучшения/оптимизации для общего случая.

PHP построен на C, некоторые из функций, просто обертками вокруг гр аналогов, например hypot поиска Google, посмотрите на man hypot, в документации, ибо он по математике Lib http://www.gnu.org/software/libc/manual/html_node/Exponents-and-Logarithms.html#Exponents-and-Logarithms

Источник фактически не дает лучшего сведения 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 функции, и нет простого способа документировать это.

Существует частичный список здесь (который я предполагаю, что вы уже видели)

List of Big-O for PHP functions

Что делает список некоторых из наиболее распространенных функций 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; 

} 

Используя тот факт, что не может быть более 1 нечетным графа, вы можете вернуться рано из массива.

I думаю, что mine также 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).

Я знаю, что многое из этого поста спекулирует о том, почему его не было, и Тереза ​​не много рисунка из достоверных источников, я надеюсь, что сво частично объяснить, почему большая разве O перечислены на странице документации, хотя