[Study] 알고리즘_시간복잡도_코딩테스트

(TMI) 최근 정말 가고싶었던 회사에 코딩테스트를 보았는데 시간복잡도 처리를 제대로 하지 못하여 시간 분배를 못하였다......

결과가 어떻든 계속 도전할거다 !! 화이팅!!!

 

시간 복잡도 유형

- 빅-오메가 : 최선일때 연산 횟수 (예 : 반복문 100번 중 0이 가깝게 끝날때)

- 빅-세타 : 보통일때 연산 횟수 (예 : 반복문 100번 중 중간쯤 끝날때)

- 빅-오 : 최악일때 연산 횟수 (예 : 반복문 100번 중 끝자락에 끝날때) : 항상 최악을 염두해두어야 한다. 

 

강의 내용 중 '빅-오' 인 최악일때를 염두해두어야 합니다.

주어지는 입력값에 조건이 주어지고 그 조건을 계산하여 횟수를 대략적으로 파악이 가능합니다.(대략 1억회 : 1초)

시간복잡도

여러가지 시간 복잡도가 있다.

알고리즘마다 시간 복잡도를 가지고 있다.

버블정렬 : n제곱

병합정렬 : nlogn

바이너리 서치 : logn

단순히 외우지 말고 계속 공부하다보면 알게된다!

 

< 산출식 >

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

 

만약 2초 안이면 2억번 미만이여야 하는데  데이터 크기가 100만이였을때

버블정렬 알고리즘 연산 횟수는 : 1000000000000 번으로 부적합 알고리즘(x) :100만 제곱

병합정렬 알고리즘 연산 횟수는 : 1000000(log1000000) 0.2초만에 정렬 가능 

 

 

내 코드가 시간 복잡도에 맞게 잘 작성되었는 지 확인!!

<기준>

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

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

</기준>

 

일반 1차원 for문 10개가 있더라도 이중 for문이 시간 복잡도에 더 영향을 준다. 

 

정리

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

2. 비효율적인 로직 찾아 효율적으로 바꾸기(예 :이중for문)

놓치는 부분 : 내가 짠 부분에 대해 문제가 없다 생각하고 알고리즘을 선택 기준에만 문제가 있다 생각하는 경우가 있음.

 

 

 

 

 

 

하루코딩 개발자님 유튜브를 보고 공부하였습니다.