알고리즘 시간 복잡도란?

시간 복잡도란?

시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수이다. 1억 번의 연산을 1초의 시간으로 간주한다.

ex) 제한시간 2초 : 2억연산 안에 답 도출

 

내가 짠 코드가 얼마나 효율적인지 > 시간복잡도로 확인 가능하다.

 

 

반응형

 

 

 

시간 복잡도 유형

1. 빅-오메가 

최선일 때의 연산 횟수이다.

 

2. 빅-세타

보통일 때 연산 횟수, 평균적인 값을 구한다.

N/2 정도의 연산 횟수.

 

3. 빅-오 (Big O)

최악일 때의 연산 횟수를 나타낸 표기법이다.

모든 경우를 가정하는 표기법이다.

 

코딩 테스트 시, 최악의 횟수를 염두에 두고 코딩 테스트에 임해야 한다. > 코딩 테스트 시 빅-오 를 사용해야함 !

 

 

 

연산 횟수 계산 방법

연산 횟수 = 알고리즘 시간 복잡도 X 데이터의 크기

주어진 데이터의 크기를 확인해서, 연산 횟수를 구하는 것이 중요하다.

 

 

 

시간 복잡도를 바탕으로 코드 로직 개선하기

1. 상수는 시간 복잡도 계산에서 제외한다.

2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.

 

* 이중 for 문 (반복문) 의 경우 N *N 으로 제곱이기 때문에 시간이 오래 걸림. 일반 for 문 10개보다 이중 for 문 하나가 더 시간이 오래걸림. 때문에, 가장 많이 중첩되는 중첩문을 기준으로 봐야한다.

 

 

 

정리

1. 알맞은 알고리즘 쓰기 (선택기준)

2. 비효율적인 로직 찾아 효율적으로 변경

 

시간 복잡도 알고리즘을 풀다보면 60프로는 이해할 수 있다 !! (나머지 40 프로는 수학공식 적용이라 ㅠㅠ)

* 빨간 부분 클릭 시 알고리즘 풀이로 이동한다

* 시간 복잡도 알고리즘 문제 모음으로 이동하기

 

 

https://www.youtube.com/watch?v=XncTU-4i1KI&t=29s