strlen()의 시간복잡도에 관하여..

문자열의 용량을 나타내 주는 strlen() 함수의 헤더 파일은 <string.h>, <cstring>이다.

이 함수는 매개변수로 string을 입력받는다.

 

이때, strlen()은 문자열의 용량을 문자열의 끝을 찾는 방법을 통해 알아낸다. 즉, 문자열의 첫 character부터 시작하여 문자열의 끝을 알리는 \n을 찾을 때까지 문자열의 용량만큼을 탐색하는 것이다.

 

따라서 이것이 반복문, 대표적으로 1중 for문과 함께 쓰인다면 그 시간 복잡도는 O(n^2)이 될 것이다.

다음은 O(n^2) 코드이다.

#include <cstring>

char a[100000];

int main(){
	
    // O(n^2)
    for(int i=0; i<strlen(a); i++){
    	... some codes ...
    }
	
    return 0;
}

 

그러나, strlen()을 변수에 할당한 뒤 할당된 변수를 for문과 함께 쓰게 되면 불필요한 time complexity를 줄일 수 있게 된다.

다음은 O(n) 코드이다.

#include <cstring>

char a[100000];

int main(){
	
    // O(n)
    int len = strlen(a);
    for(int i=0; i<len; i++){
    	... some codes ...
    }
	
    return 0;
}

 

따라서 strlen() 함수를 쓸 일이 있는 경우에는 반복문에 직접적으로 같이 쓰는 것을 피해야 한다.

위에서와 같이 간접적으로 이용하는 방법을 택해야 한다.

 

하지만, C++에서는 string의 길이 를 제공해주는 라이브러리가 있다.

바로 length() 함수인데, 이 함수는 <string> 헤더를 선언함으로써 사용할 수 있다.

 

C++11에서의 length() 함수는 시간 복잡도 O(1)을 갖게 되며, 따라서 for문에서의 사용이 제한되지 않는다.

 

#include <string>

int main(){
	
    string str;
    getline(cin, str);
    
    // O(1)
    for(int i=0; i<str.length(); i++){
    	... some codes ...
    }
	
    return 0;
}

나는 맘 편하게 str.length()를 이용하려는 편이다.

자바를 써 버릇해서 그런지 str.length()가 더 익숙한 것 같다.

 

 

참고 : http://www.cplusplus.com/reference/cstring/strlen/

strlen - C++ Reference

참고 : http://www.cplusplus.com/reference/string/string/length/

string::length - C++ Reference