Как улучшить временную сложность этого кода?
Как я могу улучшить временную сложность этого кода?
$s = "Name";
for($i=0; $i<strlen($s); $i++) {
//some code
}
Решение
Это зависит от 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);
}
Другие решения
Других решений пока нет …