我一直在谷歌过去的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的信息，但完整的列表将非常方便将来的问题。
编辑2
在研究了一般的空间和时间复杂度之后，我发现这段代码具有O(N)时间复杂度和O(1)空间复杂度，因为:
count_chars将循环N次(输入字符串的完整长度，使其开始复杂度为O(N))。这将生成一个具有有限最大字段数的数组(确切地说是26个，不同字符的数量)，然后它在该数组上应用一个过滤器，这意味着过滤器最多将循环26次。当把输入长度推到无穷大时，这个循环是不重要的，它被视为一个常数。Count也适用于这个生成的常量数组，并且由于count函数复杂度为0(1)，所以Count不重要。因此，该算法的时间复杂度为O(N)。
空间复杂度也是如此。在计算空间复杂度时，我们不计算输入，只计算过程中生成的对象。这些对象是包含26个元素的数组和count变量，它们都被视为常量，因为无论输入有多大，它们的大小都不能在这一点上增加。因此，我们可以说该算法的空间复杂度为O(1)。
无论如何，这个列表仍然是有价值的，所以我们不必查看php源代码。:)不包含此信息的可能原因是很可能在每个版本中更改，因为针对一般情况进行了改进/优化。
PHP是基于C构建的，一些函数只是简单地包装了C对应的函数，例如hypot a google search, a look at 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将有不同的实现。所以在不同的操作系统下PHP在
上编译可能会有不同的大0另一个原因可能是因为会使大多数开发人员感到困惑。我认识的大多数开发人员只会选择带有"最佳"大O的函数一个最大值并不总是意味着它更慢
http://www.sorting-algorithms.com/有一个很好的视觉支持，说明一些函数发生了什么，比如冒泡排序是一个"慢"的排序，但它是对几乎排序的数据最快的排序之一。快速排序是许多人会使用的，对于几乎排序的数据来说，这实际上是非常慢的。大0是最坏的情况——PHP可能会在应该针对特定条件进行优化的版本和可能会改变函数的大0之间做出决定，并且没有简单的方法来记录这一点。
这里有一个部分列表(我猜你已经看到了)
PHP函数的大0列表
它列出了一些更常用的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)，我实际上看不到太多其他语言的信息。
我知道这篇文章的很多人都在猜测为什么大O没有出现在文档页上，而且没有很多可靠的来源，我希望这篇文章能部分解释为什么大O没有出现在文档页上