반응형
Notice
Recent Posts
Recent Comments
Link
목록빅오표기법 (1)
안 쓰던 블로그
정말 놀라운 C++ string의 시간 복잡도
[1번 케이스] #include #include using namespace std; int main() { string s; int n = 100000; for (int i = 0;i < n;i++) { s += "A"; } return 0; } 이것은 O(N)의 복잡도가 걸린다 [2번 케이스] #include #include using namespace std; int main() { string s; int n = 100000; for (int i = 0;i < n;i++) { s = s + "A"; } return 0; } 이것은 O(N^2)의 복잡도가 걸린다 1번 케이스는 문자열 s의 마지막에 "A"가 추가되는 방식으로 돌아간다. 2번 케이스는 매번 새로운 문자열을 만든다고 할 수 있다. 즉, ..
알고리즘/Algorithm
2021. 11. 5. 15:07