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

Question

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

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

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

//some code

}

-3

algorithm php time-complexity

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

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

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

//some code

}

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

Я должен признать, что я не владею C / C ++, но я думаю, длина является простым атрибутом zend_string, то есть РНР strlen() является O (1):

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

0