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

如果知道PHP使用爆炸/内爆函数的算法，以及它们的时间复杂程度如何，我很感兴趣。PHP的爆炸/内爆时间复杂度

预先感谢您。

2012-12-28 Headshota

'O（N）'，我想。我看不出你会做得更好或更糟。 – NullUserException

@KamilTomšík-这可能在一个程序中非常重要，该程序会使大量调用在大型数据集上爆炸/爆发。如果函数是超线性的，那么在一个大程序中尝试使用这些函数是一个非常糟糕的主意，并且OP将会更好地实现它们更快。如果它们以某种方式是次线性的，那么知道它会很好，因为值得重写代码来更频繁地使用爆炸/内爆。 – templatetypedef

@KamilTomšík我需要知道使用爆炸程序的运行时间。就如此容易。 – Headshota

在string.c你可以看到算法。它起始于约1021 line ..

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

来源

2012-12-28 23:59:47

一个简单的问题 - “Z_STRLEN_P”的复杂性是什么？如果这不是O（1），那么复杂度可能更准确地为O（mn），其中n是字符串长度，m是分隔符的长度。 – templatetypedef

@templatetypedef是'O（1）'。因为'delim'是一个zval，并且这个宏指向'（zval）.value.str.val' –

根据GitHub上的PHP源代码，它是线性的。你可以检查explode()here。

来源

2012-12-29 00:00:17 mirelon

短的答案：对于单字节定界符，explode的时间complexeity是在Ο（Ñ）;但对于多字节分隔符，其时间复杂度为0（N ）。

implode显然是在Ο（N），因为它只是简单地粘在一起。

扩展答案：的basic algorithm of explode是串搜索的定界符事件和封闭的子字符串复制到一个新的数组。

要查找串的定界符的位置，它使用internal function 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+ 我）为我中号 -floor（Ñ/2）到小区（Ñ/2）

或

（ñ - 中号 1）·2 +Σ我 - ΣĴ为我从1到小区（Ñ/2），Ĵ从1到中号 -floor（Ñ/2）-1。

由于Σ我为我从1到Ñ可以通过Ñ·（Ñ 1）/ 2 =（Ñ + Ñ来表示）/ 2，我们还可以这样写：

（N-中号 1）·2 +（小区（Ñ/2） +小区（Ñ/2））/ 2 - （（中号 -floor（Ñ/2）-1 ） +（中号 -floor（ñ/2）-1））/ 2

为了简单起见，让我们假设两个ñ和中号总是偶数，所以我们可以省略小区“和'地板的：

（Ñ - 中号 1）·2 +（（Ñ/2 + 1） + Ñ/2 + 1）/ 2 - （（中号 - ñ/2-1） +（中号 - ñ/2）-1）/ 2
=（ñ - 中号 1）·2 + Ñ /8 + 3·Ñ/4 + 1 - （（中号 - Ñ/2-1） + （中号 - ñ/2）-1）/ 2

此外，我们可以估算值高达：ñ - 中号 < N and M - N/2-1 < N。因此，我们得到：

ñ·2 + Ñ /8 + 3·Ñ/4 + 1 - （Ñ + Ñ）/ 2
< ñ·2 + ñ + 4·ñ - Ñ + Ñ

这样张该explode具有多个字节定界符是在Ο（Ñ ）。

来源

2012-12-29 09:37:36 Gumbo

优秀的答案！ – Headshota

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

回答

相关问题