[Java] 알고리즘

코딩 테스트 문제를 풀기 전에 알고리즘에 대한 확실한 이해를 갖고 진행하려고 한다.

1. 시간 복잡도

알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 의미한다.
일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측한다.

시간 복잡도 정의하기

• 빅-오메가(Ω(n)) : 최선일 때 (best case)의 연산 횟수를 나타낸 표기법
• 빅-세타((Θ)) : 보통일 때 (average case)의 연산 횟수를 나타낸 표기법
• 빅-오(O(n)) : 최악일 때 (worst case)의 연산 횟수를 나타낸 표기법

🔥 주목!!
코딩 테스트에서는 빅-오 표기법을 기준으로 수행 시간을 계산하는 것이 좋다.
다양한 테스트 케이스를 수행해 모든 케이스를 통과해야만 합격으로 판단하므로 시간 복잡도는 최악일 때를 염두에 두어야 한다!

시간 복잡도 계산

시간 제한 2초 : 2억 번 이하의 연산 횟수로 문제를 해결해야 함
연산 횟수 : 알고리즘 시간 복잡도 x 데이터 크기

 

 

---

참고 자료
Do it 알고리즘 코딩 테스트 자바편

 

해당 게시글을 벨로그에서 이전된 글입니다. (https://velog.io/@yerim159/Java-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)