PHP's的时间复杂度爆炸/内爆

在string.c中可以看到算法。从1021行开始…

    if (p2 == NULL) {
    add_next_index_stringl(return_value, p1, Z_STRLEN_P(str), 1);
    } else {
    do {
        add_next_index_stringl(return_value, p1, p2 - p1, 1);
        p1 = p2 + Z_STRLEN_P(delim);
    } while ((p2 = php_memnstr(p1, Z_STRVAL_P(delim), Z_STRLEN_P(delim), endp)) != NULL &&
             --limit > 1);
    if (p1 <= endp)
        add_next_index_stringl(return_value, p1, endp-p1, 1);
    }

它只是一个单循环，所以我调用它具有O(N)复杂度。仔细检查代码。它扫描字符串并将结果添加到return_value。是的。其线性。

简答:对于单字节分隔符，explode的时间复杂度为Ο(N‍);但对于多字节分隔符，其时间复杂度为Ο(N‍²)。

implode显然在Ο(N‍)中，因为它只是将碎片粘合在一起。

扩展答案: explode的基本算法是搜索字符串中出现的分隔符，并将所包含的子字符串复制到一个新的数组中。

要查找字符串中分隔符的位置，它使用内部函数zend_memnstr (php_memnstr只是zebd_memnstr的别名)。对于单个字节，它只需调用memchr进行线性搜索(因此在Ο(N)中)。

但是对于分隔符大于一个字节的值，它调用memchr来搜索分隔符在字符串中的第一个字节的位置，测试分隔符的最后一个字节是否存在于字符串中的预期位置，并调用memcmp来检查两者之间的字节。所以它基本上检查分隔符是否包含在任何可能的位置字符串中。这听起来很像Ο(N‍²)。

现在让我们看看这个算法的最坏情况，即模式的第一个和最后一个字节都匹配，但倒数第二个字节不匹配，例如:

string:     aaaabaaaa
delimiter:  aaaaaa
aaaabaaaa
aaaaXa      (1+1+5)
 aaaX?a     (1+1+4)
  aaX??a    (1+1+3)
   aX???a   (1+1+2)

X表示memcmp和?未知字节不匹配。括号内的值是统一度量的时间复杂度。这就等于

Σ(2 + )为我从地板( N /2)来装天花板( N /2)

或

( N -‍ + 1) * 2 +Σ -Σj 我从1到装天花板( N /2), j从1到 M 地板( N /2) 1 .

我从1到N 可以表示 N ·( N + 1)/2 = ( N <一口> 2> N )/2,我们还可以写:

( N -‍ + 1)·2 +(装天花板( N /2) <一口> 2> N /2))/2 - ((地板( N /2) 1) <一口> 2> 地板( N /2) 1))/2

为简单起见，我们假设N和M总是偶数，因此我们可以省略' ceil ' s和' floor ' s:

( N -‍ + 1)·2 + (( N /2 + 1) <一口> 2> N /2 + 1)/2 - ((M -‍ N /2) <一口> 2> -‍ N /2) 1)/2
= ( N -‍ + 1) * 2 + N <一口> 2> /4 + 1 - ((M -‍ N /2) <一口> 2> -‍ N /2) 1)/2

进一步，我们可以向上估计值:N-‍M <<em>N和M-‍N/2-1 <<em> N 。这样我们得到:

N ·2 + N <一口> 2> /4 + 1 - ( N <一口> 2> N )/2
& lt; N ·2 + N <一口> 2> - N <一口> 2>

这证明了具有多字节分隔符的explode在Ο(N²)。

根据GitHub上的PHP源代码，它是线性的。点击这里查看explode()