자료구조 - 시간 복잡도 표기법

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

- 수행시간 : 1억번의 연산을 1초의 시간으로 간주하여 예측

 

- 시간 복잡도 유형

> 빅오메가 : 최선일때  1번

> 빅세타 : 보통일때  2/N 번

> 빅오 : 최악일때.  N번

 

시간복잡도 예제 코드

 

 

 

 

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

 

 

 - N개의 갯수의 숫자가 주어 졌을 경우 이를 오름차순으로 정렬하시오

  > 첫번째 줄에 수의 갯수 N개를 입력한다 (1 <= N <= 1000000)

 > 두번째 줄에서 N개의 숫자만큼 수를 입력한다. 

 > 절대값이 1000000 보다 작거나 같은 수이며 중복되지 않는다.

 

 

- 연산 횟수 계산 방법 : 알고리즘 시간 복잡도 * 데이터의 크기

 

- 알고리즘 적합성 평가

 - 버블정렬 = (1000000) ^2 = 1000000000000 > 200000000 -> 부적합 알고리즘

 - 병합정렬 = 1000000 log  (1000000) = 약 20000000 < 200000000 => 적합알고리즘

 

시간 복잡도는 작성한 코드의 비효율적인 로직을 개선하는 바탕으로 사용할 수 있다

시간복잡도 도출 기준

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

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

 

시간 복잡도는 가장 많이 중첩된 반복문을 기준으로 도출한다.

 

연산횟수가N제곱인경우

package test;

public class CountingTest {

public static void main(String[] args) {
// TODO Auto-generated method stub

int N = 100000;

int cnt = 0;

for(int i = 0; i < N; i ++) {
for (int j = 0; j < N ; j ++) {
System.out.println("연산횟수 : "+ cnt++); 
}
}

}

}