[Java] 시간복잡도

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

일반적으로 수행 시간은 1억번의 연산을 1초의 시간으로 간주어 예측한다.

 

<시간 복잡도 유형>

빅-오메가: 최선일 때의 연산 횟수를 나타낸 표기법

빅-세타: 보통일 때의 연산 횟수를 나타낸 표기

빅-오: 최악일 때의 연산 횟수를 나타낸 표기법

 

<코딩테스트에서는 어떤 시간 복잡도 유형을 사용해야 할까?>

코딩테스트에서는 빅-오 표기법을 기준으로 수행시간을 계산하는 것이 좋다.

 

 

 

<연산 횟수 계산 방법>

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

 

<시간 복잡도 도출 기준>

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

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