php - PHP的explode/implode的时间复杂度

Question

如果知道 PHP 用于爆炸/内爆函数的算法以及它们的时间复杂度是多少，我很感兴趣？

先感谢您。

Answer 1

在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. 所以是的。其线性。

Answer 2

简答：对于单字节分隔符，explode的时间复杂度在Ο( N ‍)；但是对于多字节分隔符，它的时间复杂度是Ο( N‍ <sup>2)。

implode显然在Ο( N ‍) 中，因为它只是将各个部分粘合在一起。

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

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

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

现在让我们看一下该算法的最坏情况，其中模式的第一个和最后一个字节都适合，但倒数第二个不适合，例如：

string:     aaaabaaaa
delimiter:  aaaaaa

aaaabaaaa
aaaaXa      (1+1+5)
 aaaX?a     (1+1+4)
  aaX??a    (1+1+3)
   aX???a   (1+1+2)

AX表示不匹配memcmp和?未知字节。括号中的值是统一度量的时间复杂度。这将总结为

Σ (2+ i ) for i从M -floor( N /2) 到 ceil( N /2)

或者

( N -‍<em>M+1)·2 + Σ i - Σ j对于i从 1 到 ceil( N /2), j从 1 到M - floor( N /2)-1。

由于 Σ i for i从 1 到N可以表示为N ·( N +1)/2 = ( N ² + N )/2，我们也可以写成：

( N -‍<em>M+1)·2 + (ceil( N /2) ² +ceil( N /2))/2 - (( M -floor( N /2)-1) ² +( M -地板( N /2)-1))/2

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

( N -‍<em>M+1)·2 + (( N /2+1) ² + N /2+1)/2 - (( M -‍<em>N/2-1) ² +( M -‍<em>N/2)-1)/2
= ( N -<em>M+1)·2 + N ² /8+3· N /4+1 - (( M -‍<em >N/2-1) ² +( M -‍<em>N/2)-1)/2

此外，我们可以向上估计值：N -‍<em>M < N和M -‍<em>N/2-1 < N。因此我们得到：

N ·2 + N ² /8+3· N /4+1 - ( N ² + N )/2
< N ·2 + N ² +4· N - N ² + N

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

Answer 3

根据 GitHub 上的 PHP 资源，它是线性的。你可以explode() 在这里查看。