PHP 内置函数复杂性（isAnagramOfPalindrome 函数）

我在过去的两个小时里一直在谷歌搜索，但找不到 php 内置函数时间和空间复杂度的列表。我有回文字谜 https://stackoverflow.com/questions/4628386/what-is-the-best-algorithm-to-find-whether-an-anagram-is-of-a-palindrome要解决的问题具有以下允许的最大复杂度：

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

有人知道在哪里可以找到此类信息吗？

EDIT

我发现array_filter具有 O(N) 复杂度，并且count复杂度为 O(1)。现在我需要找到有关的信息count_chars，但是完整的列表对于将来的问题会非常方便。

EDIT 2

经过对空间和时间复杂度的一些研究后，我发现这段代码具有 O(N) 时间复杂度和 O(1) 空间复杂度，因为：

The count_chars将循环 N 次（输入字符串的全长，起始复杂度为 O(N) ）。这会生成一个最大字段数有限的数组（准确地说是 26 个不同字符的数量），然后对该数组应用过滤器，这意味着过滤器最多会循环 26 次。当将输入长度推向无穷大时，这个循环是微不足道的，它被视为一个常数。计数也适用于这个生成的常量数组，而且它是微不足道的，因为count函数复杂度为 O(1)。因此，该算法的时间复杂度为O(N)。

空间复杂度也是如此。在计算空间复杂度时，我们不计算输入，只计算过程中生成的对象。这些对象是 26 元素数组和 count 变量，两者都被视为常量，因为无论输入有多大，它们的大小都不能增加超过此点。所以我们可以说该算法的空间复杂度为O(1)。

无论如何，该列表仍然很有价值，因此我们不必查看 php 源代码。 :)

不包含此信息的一个可能原因是每个版本可能会发生变化，因为针对一般情况进行了改进/优化。

PHP 是基于 C 构建的，一些函数只是 C 对应函数的包装器，例如hypot谷歌搜索，看一下man hypot，在数学库的文档中http://www.gnu.org/software/libc/manual/html_node/Exponents-and-Logarithms.html#Exponents-and-Logarithms 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 https://github.com/lattera/glibc/blob/a2f34833b1042d5d8eeb263b4cf4caaea138c4ad/math/w_hypot.c（不是官方的，只是很容易链接到）

更何况，这只是glibc，Windows会有不同的实现。所以编译 PHP 的每个操作系统甚至可能有不同的大 O

另一个原因可能是因为这会让大多数开发人员感到困惑。 我认识的大多数开发人员都会简单地选择具有“最佳”大 O 的函数

最大值并不总是意味着速度较慢

http://www.sorting-algorithms.com/ http://www.sorting-algorithms.com/

对某些函数所发生的情况有很好的视觉支持，即冒泡排序是一种“慢”排序，但它是几乎排序数据最快的排序之一。 许多人会使用快速排序，但对于接近排序的数据来说，这实际上非常慢。 Big O 是最坏的情况 - PHP 可能会在应该针对特定条件进行优化的版本和将更改函数的 Big O 的版本之间做出决定，并且没有简单的方法来记录这一点。

这里有一个部分列表（我想你已经看过了）

PHP 函数的 Big-O 列表 https://stackoverflow.com/questions/2473989/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 think我的也是 O(N) 时间，因为据我所知，最坏的情况是 O(N) 。

Test

$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

Your way

Took 112.96145009995 seconds, 262144 memory

我相当确定我的方法也不是最快的方法。

实际上，除了 PHP（例如 Java）之外，我看不到太多其他语言的信息。

我知道这篇文章的很多内容都在猜测为什么它不存在，并且没有太多来自可靠来源的绘图，我希望它部分解释了为什么大 O 没有在文档页面中列出