[알고리즘] 복잡도

복잡도

알고리즘의 성능을 나타내는 척도

동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을수록 좋은 알고리즘

 

공간 복잡도

특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

 

시간 복잡도

시간 복잡도란 문제를 해결하는데 걸리는 시간과 입력의 함수 관계이다.

알고리즘의 시간 복잡도는 주로 빅-오 표기법을 사용하며 빅-오표기법은 계수와 낮은 차수의 항을 제외시키는 방법이다.

간단하게 표현하자면 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석한 것

빅 오메가 : 최선일 때

빅 세타 : 보통일 때

빅 오 : 최악일 때

 

# 100 미만의 랜덤 숫자 n이 있고, n을 구하기 위해 100번 반복하는 반복문을 작성한 경우

빅 오메가 → n이 0인 경우이므로 1

빅 세타 → 평균치이므로 n/2

빅 오 → 최악의 경우 범위 내 제일 마지막 숫자이므로 n

 

▶ 코딩테스트를 진행할 때 최악의 경우인 빅 오를 기준으로 수행시간을 계산하여 알고리즘을 설계

 

빅 오 표기법 Big-O Notaion

가장 빠르게 증가하는 항만을 고려하는 표기법, 함수의 상한만을 나타내게 됨

연산 횟수가 3N^3 + 5N^2 + 1,000,000 알고리즘 → 차수가 가장 큰 항만 남기므로 O(N^3)으로 표기

 

시간 복잡도 계산해 보기

N개의 데이터의 합을 계산하는 프로그램

int[] arr = {1, 2, 3, 4, 5}; // 5개의 데이터 N = 5
int sum = 0; // 합계를 저장할 변수

// 모든 데이터를 하나씩 확인하며 합계 계산
for(int i = 0; i < arr.length; i++){
    sum += arr[i];
}

// 결과 출력
System.out.println(sum);

수행시간은 데이터의 개수 N에 비례하므로 시간복잡도는 O(N)

모든 데이터를 하나씩 확인하며 합계를 계산하는 부분이 성능에 많은 영향

 

2중 반복문을 이용하는 프로그램

int[] arr = {1, 2, 3, 4, 5};

for(int i = 0; i < arr.length; i++){
    for(int j = 0; j < arr.length; j++){
        System.out.println(arr[i] * arr[j]);
    }
}

시간 복잡도는 O(N^2)

모든 2중 반복문이 O(N^2)인 것은 아님 내부에 다른 함수를 호출한다면 함수의 시간 복잡도도 고려

 

알고리즘 설계 TIP

일반적으로 1억 번의 연산 횟수 = 약 1초 소요

코딩 테스트 문제에서 시간제한은 통상 1~5초가량, 명시되지 않았다면 대략 5초 정도라고 생각

 

요구사항에 따라 적절한 알고리즘 설계하기

시간제한(수행시간 요구사항)을 제일 먼저 확인

# 시간제한이 1초인 문제