秩序的标准库函数

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 - 它接收到第一个字符的地址，并且必须通过扫描字符串来查找空字符，并且它只能通过前进和检查每个字符来查找空字符。

Answer 2

某些函数在标准中定义了其复杂性。其他人，包括那些从C继承而来的人，没有。对于那些人来说，除了执行质量以外，你不能依赖其他任何东西来保持最低限度。

Answer 3

是的，strlen是O（n），但在这个特定的示例中（使用字符串文字），优化器可以用代替sizeof(buf)。有些编译器可以。