알고리즘 2주차( 알고리즘의 효율성 분석)

시간 복잡도란?

- 알고리즘이 얼마나 빨리 수행되는지를 나타내는 것

공간 복잡도란?

- 알고리즘이 수행되는 동안 요구되는 메모리 공간의 크기

 

알고리즘은 3가지로 분석할 수 있다

- 입력크기, 실행 시간 측정 단위, 증가 차수

 

입력 크기

- 배열의 크기

- 연결 목록의 길이

- 행렬에서 행과 열의 크기

- 그래프에서 정점과 간선의 수

덕수궁에서 창덕궁을 가는데 가장 빠른 길은 어떻게 찾아야 할까?

일단 갈 수 있는 루트들을 모두 조사해보자

덕수궁 - 경희궁 - 경복궁 - 창덕궁

덕수궁 - 경복궁 - 창덕궁

덕수궁 - 종묘 - 창덕궁

 

덕수궁 - 경희궁 - 경복궁 루트는 1 + 0.7 = 1.7로 덕수궁 -경복궁 = 1.3보다 크기때문에 제외한다.

덕수궁 - 경복궁 - 창덕궁 = 3.4 > 덕수궁 - 종묘 - 창거궁 = 3.5

따라서 덕수궁 - 경복궁- 창덕궁 = 3.4가 가장 ㅈ빠른 루트임을 알 수 있다.

 

위 코드의 알고리즘은

입력크기 : n

기본연산 : sum += i*j

시간 복잡도 : n*(n + 1)/2 -> n^2

 

 

증가 차수란

시간 복잡도 함수의 입력 크기(N)에 따른 증가율을 의미한다.

 실행 시간은 입력 크기가 작으면 거의 차이가 없다.

–로그 함수(〖log〗_2 𝑁): N의 값이 4배 증가할 때 2만큼 증가

–1차 선형 함수(N): N의 값에 비례하여 증가

–2차 선형 함수(N^2): N의 값이 4배 증가할 때 16배 증가

–지수 함수(2^N): N의 값이 4배 증가할 때 2의 4 제곱배 증가

 

시간 복잡도의 분류 - 최악, 평균, 최선의 경우

최악 경우(worst-case) 시간 복잡도

–모든 입력에 대해서 기본 연산이 수행되는 최대 횟수

최선 경우(best-case) 시간 복잡도

–모든 입력에 대해서 기본 연산이 수행되는 최소 횟수

평균 경우(average-case) 시간 복잡도

–모든 입력에 대해서 기본 연산이 수행되는 평균 횟수

–일반적으로 최악 경우보다 구하기가 어려움

 

빅 O 표기법

O(1) - 상수 시간

O(log n) -  로그(대수) 시간

O(n) - 선형 시간

O(n log n) -  로그 선형 시간

O(n2) - 제곱 시간

O(n3) - 세제곱 시간

O(2n) - 지수 시간

 

public static void main(String[] args){

       Scanner sc = new Scanner(System.in);

       int n = sc.nextInt();

       int square = 0;

// square = n * n;

//for(int i=0; i < n; i++){

// square += square;

//}

       for(int i=0; i < n; i++){

             for(int j=0; j < n; j++){

                   square += 1;

             }

       } 

       System.out.print(square);

}

 

 

 

 

 

위 알고리즘을 개선해보자. CUME[]를 계산하는 과정에서 중복계산이 되고있다 이를 제거하고 효율적으로 돌아가도록 빠른 알고리즘을 만들어 보자.