O(1)时间复杂度如何判断一个字符串是否过长？

Question

我正在尝试查看字符串是否超过 10,000 个字符。如果是，它应该打印 too long。我知道我可以用 strlen 来做到这一点，但是时间复杂度是 O(n)，这还算不错，但是如果有人输入 10,000 个字符，我仍然必须每次迭代 10,000 个字符，但是如果我的人输入了 100 万个字符，那就太糟糕了 n。所以我的解决方案是，检查是否设置了第 10,001 个字符。如果设置了，那么它显然太长了。这行得通吗？或者这有时会起作用（并且取决于内存 was/is 的分配方式）。

Answer 1

使用substr

substr(yourString, lengthConstraint, 1);

Answer 2

<?php 
if (isset($str[100001])) { 
     ... do my stuff ... 
} ?>

isset 函数是运行 on $str[10001]，它只是数组中的一个地址，因此是 o[1]。此外，在 php 中访问索引外的键时，它不会抛出错误或导致内存泄漏。它抛出一个 OutOfBoundsException 异常，可以用 try catch 块捕获。

Answer 3

strlen 的时间复杂度已经是 O(1)，因为长度只是简单地存储为一个属性。

http://php.net/manual/en/function.strlen.php

Answer 4

I know I can do this with strlen, but then the time complexity is O(n)

不知道是谁告诉你的，strlen就是returns len 属性.

strlen的定义，它使用ZSTR_LEN宏来获取字符串长度

ZEND_FUNCTION(strlen)
{
    zend_string *s;

    ZEND_PARSE_PARAMETERS_START(1, 1)
        Z_PARAM_STR(s)
    ZEND_PARSE_PARAMETERS_END();

    RETVAL_LONG(ZSTR_LEN(s));
}

以及ZSTR_LEN

的定义

#define ZSTR_LEN(zstr) (zstr)->len

O(1)时间复杂度如何判断一个字符串是否过长？

How to determine if a string is too long in O(1) time complexity?

php

strlen