[Java] 01. 시간 복잡도

🧑🏻‍💻 하루코딩 님의 Do it! 알고리즘 코딩테스트 강의(인프런)를 듣고 정리한 내용입니다. 

 

01. 알고리즘 선택의 기준이 되는 시간 복잡도 

➡️ 알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 의미한다.

➡️ 일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측한다.
    (만약 시간제한이 2초라면 2억 연산 안에 답이 나와아한다는 것)

 

 

✔️ 시간 복잡도 유형 

1. 빅-오메가(Ω(n)) : 최선일 때의 연산 횟수를 나타내는 표기법
2. 빅-세타(Θ(n)) : 보통일 때의 연산 횟수를 나타내는 표기법
3. 빅-오(O(n)) : 최악일 때의 연산 횟수를 나타내는 표기법 

※ 실제 코딩 테스트에서 염두해야 할 표기법은? 빅-오(O(n))
    → 다양한 테스트 케이스를 수행해 모든 케이스를 통과해야만 합격으로 판단하기 때문에 

 

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

   단순하게 외우는 게 아니라 공부를 하다보면 알고리즘 원리에 따라 시간 복잡도를 분석할 수 있다.

 

 

02.  시간 복잡도 활용하기

✔️ 코딩 테스트 문제에서 입력 조건에 주어진 데이터 크기와 제한 시간을 사용하여 시간 복잡도를 구한 뒤 알맞은 알고리즘을 찾을 수 있다. 

책에서는 백준 2750이라고 되어 있으나 실제로 똑같은 문제는 2751번

• 항상 최악일 때를 염두해야하기 때문에 주어진 최댓값을 기준으로 하여 시간 복잡도를 따져주어야 한다. 

 

 

✔️ 시간 복잡도를 바탕으로 작성한 코드 로직을 개선할 수 있다. 

• 시간 복잡도 도출 기준
  1. 상수는 시간 복잡도 계산에서 제외한다.
  2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.