如何提高此代碼的時間複雜度？

Question

如何提高此代碼的時間複雜度？

$s = "Name"; 
    for($i=0; $i<strlen($s); $i++) { 

    //some code 

    } 

Answer 1

這取決於PHP的Strings和strlen()的實現。如果它是O（n）（它在GNU的C strlen()中），OP代碼的複雜度將是O（n 2）。移動strlen()跳出循環會在這種情況下提高至O（N）：

$length = strlen($s); 
for($i=0; $i<$length; $i++) { 

//some code 

} 

---

然而，如果的strlen()複雜度爲O（1）（e.g. C++），該代碼是在爲O（n ），你無法再改進它。

我不得不承認，我是不流利的C/C++，但我想長度爲a zend_string的簡單屬性，即PHP's strlen()是O（1）：

ZEND_FUNCTION(strlen) 
{ 
    zend_string *s; 
    // [..] 
    RETVAL_LONG(s->len); 
}