c++ - 标准库函数的复杂度顺序

Question

抱歉，如果这是一个愚蠢的问题，但是......

此代码的复杂度为 O(n):

char buf[] = "hello world";
size_t length = strlen(buf);

for(size_t i = 0; i < length; i++)
{
    //do stuff
}

这个代码是 O(n^2):

char buf[] = "hello world";
for(size_t i = 0; i < strlen(buf); i++)
{
    //do stuff
}

因为 strlen 是 O(n)。

但是谁说strlen是O(n)的，难道标准里有定义，就一定要O(n)吗？

我如何确定知道任何标准函数的复杂度顺序是什么？

Answer 1

是的，it has to be at least O(n) by design - 它接收第一个字符的地址，必须通过沿字符串扫描来找到空字符，并且只能通过前进和检查每个字符来实现。