PHP的爆炸/內爆時間複雜度

Question

如果知道PHP使用爆炸/內爆函數的算法，以及它們的時間複雜程度如何，我很感興趣。

預先感謝您。

Answer 1

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

Answer 2

根據GitHub上的PHP源代碼，它是線性的。你可以檢查explode()here。

Answer 3

短的答案：對於單字節定界符，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具有多個字節定界符是在Ο（Ñ ）。