PHP 内置函数复杂度(isAnagramOfPalindrome 函数) [英] PHP built in functions complexity (isAnagramOfPalindrome function)

问题描述

过去 2 小时我一直在使用谷歌搜索，但找不到内置函数时间和空间复杂度的 php 列表.我有 isAnagramOfPalindrome 以下列最大允许复杂度解决的问题:

I've been googling for the past 2 hours, and I cannot find a list of php built in functions time and space complexity. I have the isAnagramOfPalindrome problem to solve with the following maximum allowed complexity:

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 是输入字符串长度.这是我最简单的解决方案，但我不知道它是否在复杂性限制内.

where N is the input string length. Here is my simplest solution, but I don't know if it is within the complexity limits.

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

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

Anyone have an idea where to find this kind of information?

编辑

我发现 array_filter 的复杂度为 O(N)，而 count 的复杂度为 O(1).现在我需要找到关于 count_chars 的信息，但是完整的列表对于以后的问题非常方便.

I found out that array_filter has O(N) complexity, and count has O(1) complexity. Now I need to find info on count_chars, but a full list would be very convenient for future porblems.

编辑 2

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

After some research on space and time complexity in general, I found out that this code has O(N) time complexity and O(1) space complexity because:

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

The count_chars will loop N times (full length of the input string, giving it a start complexity of O(N) ). This is generating an array with limited maximum number of fields (26 precisely, the number of different characters), and then it is applying a filter on this array, which means the filter will loop 26 times at most. When pushing the input length towards infinity, this loop is insignificant and it is seen as a constant. Count also applies to this generated constant array, and besides, it is insignificant because the count function complexity is O(1). Hence, the time complexity of the algorithm is O(N).

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

It goes the same with space complexity. When calculating space complexity, we do not count the input, only the objects generated in the process. These objects are the 26-elements array and the count variable, and both are treated as constants because their size cannot increase over this point, not matter how big the input is. So we can say that the algorithm has a space complexity of O(1).

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

Anyway, that list would be still valuable so we do not have to look inside the php source code. :)

推荐答案

不包含此信息的一个可能原因是每个版本可能会更改，因为针对一般情况.

A probable reason for not including this information is that is is likely to change per release, as improvements are made / optimizations for a general case.

PHP 是建立在 C 之上的，有些函数只是对 C 对应物的包装，例如 hypot google 搜索，看看 man hypot，在他数学库的文档http://www.gnu.org/software/libc/manual/html_node/Exponents-and-Logarithms.html#Exponents-and-Logarithms

PHP is built on C, Some of the functions are simply wrappers around the c counterparts, for example hypot a google search, a look at man hypot, in the docs for he math lib http://www.gnu.org/software/libc/manual/html_node/Exponents-and-Logarithms.html#Exponents-and-Logarithms

来源实际上没有提供更好的信息https://github.com/lattera/glibc/blob/b1042d5d8eeb263b4cf4caaea138c4ad/math/w_hypot.c"math/w_hypot.c(非官方，只是易于链接)

The source actually provides no better info https://github.com/lattera/glibc/blob/a2f34833b1042d5d8eeb263b4cf4caaea138c4ad/math/w_hypot.c (Not official, Just easy to link to)

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

Not to mention, This is only glibc, Windows will have a different implementation. So there MAY even be a different big O per OS that PHP is compiled on

另一个原因可能是因为它会使大多数开发人员感到困惑.我认识的大多数开发人员只会选择一个具有最佳"大 O 的函数

Another reason could be because it would confuse most developers. Most developers I know would simply choose a function with the "best" big O

最大值并不总是意味着它更慢

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

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

Has a good visual prop of whats happening with some functions, ie bubble sort is a "slow" sort, Yet its one of the fastest for nearly sorted data. Quick sort is what many will use, which is actually very slow for nearly sorted data. Big O is worst case - PHP may decide between a release that they should optimize for a certain condition and that will change the big O of the function and theres no easy way to document that.

这里有部分列表(我猜你已经看到了)

PHP 函数的 Big-O 列表

其中列出了一些更常见的 PHP 函数.

Which does list some of the more common PHP functions.

对于这个特定的例子......

无需使用内置函数即可轻松解决.

Its fairly easy to solve without using the built in functions.

示例代码

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 个奇数的事实，您可以从数组中提前返回.

Using the fact that there can not be more than 1 odd count, you can return early from the array.

我认为我的也是 O(N) 时间，因为据我所知，最坏的情况是 O(N).

I think mine is also O(N) time because its worst case is O(N) as far as I can tell.

测试

$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));

使用非常旧的硬件运行测试我的方式

Tests run using really old hardware My way

Took 64.125452041626 seconds, 262144 memory

你的方式

Took 112.96145009995 seconds, 262144 memory

我很确定我的方法也不是最快的方法.

I'm fairly sure that my way is not the quickest way either.

对于 PHP 以外的语言(例如 Java)，我实际上看不到太多信息.

I actually cant see much info either for languages other than PHP (Java for example).

我知道这篇文章的很多内容都在猜测为什么它不在那里，并且从可靠来源中提取的内容不多，我希望它可以部分解释为什么文档页面中没有列出大 O

I know a lot of this post is speculating about why its not there and theres not a lot drawing from credible sources, I hope its an partially explained why big O isnt listed in the documentation page though

这篇关于PHP 内置函数复杂度(isAnagramOfPalindrome 函数)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！