이 바보 같은 질문 인 경우

Question

죄송 표준 lib 디렉토리 기능의 복잡성의 주문,하지만 ...

이 코드의 복잡성의 순서는 (n)이 O입니다 :

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)이지만,이 특별한 예에서는 (문자열 리터럴을 사용하여) 좋은 옵티마이 저는 strlen(buf)을 sizeof(buf)으로 바꿀 수 있습니다. 일부 컴파일러는 않습니다.