Сложность встроенных функций 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).

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

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

PHP построен на C, некоторые функции являются просто обёртками вокруг аналогов c, например hypot поиск в Google, взгляд на man hypot, в документах по математике
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).

Я знаю, что многие из этого поста размышляют о том, почему его там нет, и, тем не менее, мало что почерпнуто из достоверных источников.