C++ String 사용할 때, 시간복잡도 줄이는 법

 

 

문자열 s  뒤에 "A"를 10만 번  더하는 경우, 아래 케이스에서 for 연산을 10만 번 반복합니다.

 

 

1번 케이스 

 

함수실행시간  :  0.004013s

#include <iostream>
#include <string>
#include <ctime>

using namespace std;


int main() {
    clock_t start, finish;
    double duration;
    string s;
    int n = 100000;
    start = clock();
    
    for (int i = 0; i < n;i++) {
        s += "A";
    }

    finish = clock();
    duration = (double)(finish - start) / CLOCKS_PER_SEC;
    cout << duration;
    return 0;
}

 

 

 

2번 케이스

 

함수실행시간  :  0.743712s

#include <iostream>
#include <string>
#include <ctime>

using namespace std;


int main() {
    clock_t start, finish;
    double duration;
    string s;
	
    int n = 100000;
	
    start = clock();
    for (int i = 0;i < n;i++) {
        s = s + "A";
    }
	
    finish = clock();
	
    duration = (double)(finish - start) / CLOCKS_PER_SEC;
    cout << duration;
    return 0;
}

 

 

1번 케이스는 O(N)의 시간복잡도, 2번 케이스는 O(N^2)의 시간복잡도를 가집니다.

 

1번 케이스는 문자열 s의 마지막에 "A"가 추가되는 방식으로 돌아갑니다. 2번 케이스는 매번 새로운 문자열을 만든다고 할 수 있습니다. 즉, 2번 케이스는 1번 케이스의 연산을 n번 더 실행하게 되므로 위와 같은 시간복잡도를 가지게 됩니다.

 

 

 

결론은 C++에서 문자열 뒤에 문자를 추가할 때, += 을 사용해야 실행시간을 줄일 수 있습니다.

 

 

 

 

 

 

참고자료

정말 놀라운 C++ string의 시간 복잡도