秩序的標準庫函數

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)。有些編譯器可以。