[C++코테] 시간복잡도(Time Complexity)

알고리즘이란?

- 유한한 수의 규칙에 따라 구별 가능한 기호들을 조작해서, 입력 정수에서 출력 정수를 생성하기 위한 일반화된 작업을 정의하는 일

 

연산횟수 측정 - Big O notation (빅 오 표기법)

보통 최악의 경우를 기준으로 체크를 한다. 또한 최고차항만 남기는데 어떤 코드가 N^2 + 3N + 5의 연산 시간을 가진다고 할 때, 뒤의 3N + 5같은 상수항들은 전부 무시되고 N^2만 체크하는 것이다. 

 

 

 

 

- BST (Binary Search Tree)의 원소 탐색 시간 복잡도는 O(log N)이다. 이렇게 매번 탐색 대상이 반절로 줄어드는 경우는 O(log N)의 시간 복잡도를 갖고 있다. merge sort의 merge, binary search 등등

 

- 동전 N개를 던졌을 때 경우의 수는 O(N^2)이다. 

 

 

 

 

동일한 동작을 하는 것 처럼 보이나 시간 복잡도가 다른 경우??

- 정렬된 것 vs 정렬되지 않은 것

- vector와 dictionary/set에서 키의 존재 유무

- vector와 list에서 특정 위치의 원소 가져오기 등등

시간 복잡도 내용 깃허브 링크: https://github.com/dremdeveloper/codingtest_cpp/tree/main/performance

 

 

 

https://www.inflearn.com/course/lecture?courseSlug=cpp-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%95%A9%EA%B2%A9&unitId=225756&tab=curriculum

학습 페이지

 

 

#코딩테스트합격자되기