[Step 1] 시간 복잡도

 

1. 시간 복잡도

 ==> 입력값에 따른 연산횟수를 측정하여 알고리즘의 성능을 지표로 나타냄.

 - 코딩 테스트에서는 최악의 경우를 기준으로 연산횟수를 정하는게 합리적!

2. 점근적 표기법 ==> 정확한 연산횟수 x 연산 횟수 추이만!

N이 무한으로 커지면 n^2를 제외한 나머지는 의미가 없을정도로 작음

==> 이때 최악의 경우를 고려해 점근적 표기법으로 나타낸 것이 빅오 표기법 
EX) O(N^2)

 

이 우선순위에 따라 최고차항을 제거하자!

3. 자주 보이는 복잡도

1차원 배열 탐색

2차원 배열 탐색

이진트리의 복잡도

왼쪽 문제 같은 경우 입력값이 많으므로 생각 안하고 이중 for문을 돌리면 코테에서는 틀린다. 따라서 더욱 효율적인 알고리즘을 생각하여 문제를 풀어야 한다. 오른쪽 문제는 입력값이 적으므로 성능이 상관이 없으므로 문제에서 요구하는 로직만 맞으면 정답 처리가 된다

 

 

출처 

[지금 무료] 코딩 테스트 합격자 되기 - C++ 강의 | dremdeveloper - 인프런