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

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

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

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

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

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

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

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

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

Ответы

Ответ 1

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

PHP построен на C. Некоторые из функций - это просто обертки вокруг c-аналогов, например hypot поиск google, просмотр man hypot, в документах для него math 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 функции, и нет простого способа документировать это.

Здесь есть частичный список (который, как я думаю, вы видели)

Список функций 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;

}

Используя тот факт, что не может быть больше 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 не указан на странице документации, хотя