我一直在谷歌过去的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没有出现在文档页上