Ska*_*tch 21 php time-complexity space-complexity
我一直在谷歌搜索过去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函数复杂度是O(1).因此,算法的时间复杂度为O(N).
它与空间复杂性相同.在计算空间复杂度时,我们不计算输入,只计算过程中生成的对象.这些对象是26个元素的数组和count变量,两者都被视为常量,因为它们的大小在这一点上不会增加,无论输入有多大.所以我们可以说该算法的空间复杂度为O(1).
无论如何,该列表仍然有价值,所以我们不必查看php源代码.:)
不包含此信息的一个可能原因是，随着针对一般情况的改进/优化，每个版本的信息可能会发生变化。
PHP 是基于 C 构建的，一些函数只是 C 对应函数的包装器，例如，在数学库的文档中
hypot进行 google 搜索、查看http://www.gnu.org/software/libc/manual /html_node/指数和对数.html#指数和对数man hypot
来源实际上没有提供更好的信息 https://github.com/lattera/glibc/blob/a2f34833b1042d5d8eeb263b4cf4caaea138c4ad/math/w_hypot.c（不是官方的，只是很容易链接到）
更何况，这只是glibc，Windows会有不同的实现。所以编译 PHP 的每个操作系统甚至可能有不同的大 O
另一个原因可能是因为它会让大多数开发人员感到困惑。我认识的大多数开发人员都会简单地选择具有“最佳”大 O 的函数
最大值并不总是意味着速度较慢
http://www.sorting-algorithms.com/
对某些函数所发生的情况有很好的视觉支持，即冒泡排序是一种“慢”排序，但它是几乎排序数据最快的排序之一。许多人会使用快速排序，但对于接近排序的数据来说，这实际上非常慢。Big O 是最坏的情况 - PHP 可能会在应该针对特定条件进行优化的版本和将更改函数的 Big O 的版本之间做出决定，并且没有简单的方法来记录这一点。
这里有一个部分列表（我想你已经看到了）
其中列出了一些更常见的 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 没有在文档页面中列出