Как улучшить временную сложность этого кода?

Question

Как я могу улучшить временную сложность этого кода?

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

    //some code 

    } 

Answer 1

Это зависит от реализации PHP строк и strlen(). Если это O (n) (который находится в GNU C strlen()), сложность кода OP будет O (n²). Перемещение strlen() из петли улучшило бы к O (N), в данном случае:

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

//some code 

} 

---

Однако если сложность strlen() представляет собой О (1) (e.g. C++), код в O (п), и вы больше не сможете его улучшить.

Я должен признать, что я не владеет C/C++, но я предполагаю, что длина простой атрибут zend_string, т.е. PHP's strlen() является O (1):

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