시간복잡도

알고리즘 문제를 해결할 때, 가장 좋은 방식은 문제를 이해하고 어떤 자료구조를 사용하여 해결할 것인가에 대한 사고과정이 중요합니다. 알고리즘을 선택하는 기준으로 시간복잡도를 고려해야 하기 때문에 오늘은 이에 대해서 공부해보겠습니다. 자료구조를 알고 사용하는 것이 중요하지만, 각 자료구조마다 사용되는 시간 복잡도가 어느정도인지를 알면 선택에 있어 더 효율적인 방향을 잡을 수 있습니다.

하루 만에 모든 시간복잡도에 대한 공부와 예시를 들기는 어렵기 때문에,,, 기본 개념만 잡아두고, 앞으로 공부를 하면서 해당 복잡도에 관한 알고리즘을 풀게 되면 예시로 들면서 내용을 추가하겠습니다.

1. 시간복잡도 표기법 알아보기

먼저 알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말합니다. 일반적으로 수행시간은 1억번의 연산을 1초의 시간으로 간주하여 예측합니다. 

예를 들어, 문제를 푸는데 시간제한 1초라면, 해당 문제를 풀기위해 진행하는 연산횟수가 1억번을 넘으면 안된다는 것입니다.

시간복잡도의 유형

1. 빅-오메가(Ω(n)) : 최선일 때 연산 횟수
2. 빅-세타  (Θ(n)) : 보통일 때 연산 횟수
3. 빅-오     (O(n)) : 최악일 때 연산 횟수

코딩테스트를 준비하시는 분들은 아시겠지만, 작성한 프로그램을 제출했을 때, 한 가지의 테스트케이스로 테스트가 끝나지 않습니다. 여러가지 테스트 케이스로 프로그램을 실행해보면서 정확성과, 효율성을 판단하기 때문에 프로그램에서 시간 복잡도는 가장 최악의 경우도 테스트 케이스를 무난히 통과할 수 있도록 빅-오(O(n))표기법을 기준으로 수행시간을 계산해야 합니다. 

빅오 표기법 

알고리즘의 성능을 수학적으로 표기해주는 표기법으로, 시간&공간복잡도를 파악 가능합니다.

[핵심]

ㄴ> 상수는 과감하게 버립니다. 

ㄴ> 빅오 표기법은 실제 알고리즘의 러닝타임을 측정하기 위함이 아닙니다. 장기적으로 데이터가 증가함에 따라 처리 시간의 증가율을 예측하기 위한 표기법입니다. 상수는 고정된 숫자이기 때문에 입력 데이터수(n)가 증가하여 증가율에 영향을 미칠때, 언제나 고정된 상수의 크기만큼 영향을 미치기 때문에 데이터와 함께 증가하지 않는 숫자(상수)는 생각하지 않겠다는 뜻입니다.  

ㄴ> O(2n) -> O(n), O(2n^2) -> O(n^2)

 

O(1) : constant time

입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸립니다. 예를 들어 다음과 같은 코드를 보겠습니다.

boolean cons(int[] n) {
    return (n[0] == 0 ? true : false);
}

입력으로 들어오는 배열n의 크기와 상관없이 반환값은 무조건 true 또는 false만 나옵니다.  즉, 입력데이터의 크기에 상관없이 일정한 시간이 소요됩니다. 

O(n) : linear time

입력 데이터의 크기에 비례해서 처리시간이 걸리는 알고리즘

int n[] = {1, 2, 3, 4, 5, 6, 7};
for(int i=0; i < n.length();i++) {
    System.out.println(i);
}

O(n^2) : quadratic time

for(int i = 1; i <= 9 ; i++) {
    for(int k=1; k<=9 ; k++) {
        System.out.println(i * k);
    }
}

n번의 입력값이 들어왔을때, n번의 반복을 2중으로 중첩하는 경우입니다.

위의 예시는 보시면 아시겠지만, 구구단을 출력하는 프로그램입니다. 입력데이터가 9일때, 연산횟수가 9^2입니다.

 

O(nm) : quadratic time

알고리즘을 풀면서, 2중 중첩 반복문을 푼다면 가장 많이 보게되는 유형입니다. 위와는 원리는 같지만 입력데이터가 명확히 다르기 때문에 구분은 해주셔야 합니다. 

for(int i = 1; i<=5 ; i++) {
    for(int k=1; k<=9 ; k++) {
        System.out.println(i * k);
    }
}

단순하게 구구단을 1단 부터 5단까지 구하는 예시입니다. 입력 데이터가 5와 9일때, 연산횟수는 5*9입니다.

 

O(n^3)

n의 크기만큼 3중 중첩 반복문

O(2^n)

피보나치수열, 재귀함수(한번 함수를 호출할때마다 2번씩 함.)

O(logn)

이진 검색 한 번 처리가 진행될때마다 검색할 데이터의양이 절반씩 줄어듬