标准lib函数的复杂性顺序

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

是的,它必须至少是O(n)设计 - 它接收第一个字符的地址,并且必须通过沿着字符串扫描找到空字符,它只能通过推进和检查每个字符来实现.