뭐 그럭 저럭

1. 시간복잡도와 공간복잡도 본문

컴퓨터과학 : 개념편/Data Structure & Algorithm

1. 시간복잡도와 공간복잡도

xxxelppa xxxelppa 2017.05.25 10:28



자료구조의 내용과 분류




1. 시간복잡도와 공간복잡도


우선 시간복잡도가 무엇인지에 대해서 생각해보자.

시간이 복잡한 정도라는게 무슨 의미일까?

결론부터 얘기하면 시간이 얼마나 걸리냐라는 것이다.

'시키는거 잘하는 컴퓨터가 시키는걸 그냥 하면 될건데 왜 그런것 까지 고려해야하죠?'

오래걸리면 오래 걸릴수록 이 컴퓨터가 그 작업이 CPU를 점유하는 시간이 길어지고

그 말은 CPU가 다른 일을 하지 못하기 때문에 그만큼 손해라는 것이다.

그리고 체감상 작업이 오래 걸리기 때문에, 모로가도 서울로만 가면 되는건 아니라는 것이다.


그렇기 때문에 어떠한 프로그램을 작성할 때 시간복잡도 측면에서의 성능도 고려해서 작성해야 한다는 것이다.


그렇다면 이 시간복잡도가 뭔지는 알겠는데,

무엇을 기준으로 표현을 할까?

그냥 단순하게 "이게 저거보다 빨라요"라고 하면 되는 것일까?


그래서 여기엔 분명한 기준이 존재하는데, 보통 우리는 시간복잡도를 세가지 기준을 가지고 표현한다.

관심있는 사람들은 흔히 들어봤을 빅오 표기법이 그 대표적인 예이다.

빅오 표기법 이라는 것은 점근적 상한에 대한 것인데, 이렇게 접근하면 너무 어렵다.


쉽게 접근하자.

보통 등급을 나눌때 우리는 상, 중, 하 를 사용한다.

시간복잡도에도 상중하가 있다.

상은 상한으로 '네가 아무리 오래 걸려봤자 이정도 시간 안에는 끝나'

중은 동등으로 '너 하는거 보니까 보통 이정도 걸리더라'

하는 하한으로 '네가 아무리 빨라봤자 이정도 시간은 걸려'

이렇게 생각하면 조금 받아들이기 쉬울까?


여기에 '점근적'이라는 말이 붙는 이유에 대해 생각해보자.

점근적이란 사전적 의미로 점점 가까워짐을 의미한다.

어디에 가까워 진다는 것일까?

만약 어떠한 반복문이 n번 반복한다라고 했을 때, 이 n이 무한대로 커진다면 어느 값에 가까워 지느냐 문제이다.

수학적인 극한에 대해서는 여기서 다루기 어렵다.


아래 그래프는 순서대로 점근적 상한, 하한, 동등에 대해 표현한 것이다.


조금 딱딱하게 각각의 정의에 대해 살펴보면

상한 : n0보다 큰 특정 n값에 대해 f(n) ≤ c * g(n) 을 만족하는 양의 상수 c와 n0가 존재하면 f(n) = O(g(n)) 이다.

하한 : n0보다 큰 특정 n값에 대해 f(n) ≥ c * g(n) 을 만족하는 양의 상수 c와 n0가 존재하면 f(n) = Ω(g(n)) 이다.

동등 : n0보다 큰 특정 n값에 대해 d * g(n) ≤ f(n) ≤ c * g(n) 을 만족하는 양의 상수 c, d와 n0가 존재하면 f(n) = Θ(g(n)) 이다.



이 세가지 개념중에서 가장 많이 사용하는 것은 무엇일까?

이미 알고 있겠지만 당연히 상한값이다.

왜냐면 무언가를 할 때 항상 최악의 경우를 고려해야지, 맘처럼 안되는 우리 삶에서 최상의 경우만을 고려하는

그런 이상적인 일은 존재하기 어렵기 때문이다.


그런 이유로 점근적 상한, 빅오 표기에 대해서 많이 들어본 것이다.

그렇다고 다른 개념에 대해서 존재를 모르고 넘어가서는 안된다고 생각한다.



그럼 다음으로 가장 많이 사용하는 점근적 상한값의 계산 방법에 대해 알아보자.

처음 예로 들때는 simple is best 라고 했던가, 간단할수록 좋다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.Scanner;
 
public class Example {
    public static void main(String[] ar) {
 
        Scanner sc = new Scanner(System.in);
 
        System.out.print("몇번 반복 하시겠습니까? : ");
        int n = sc.nextInt();
 
        for(int i = 0; i < n; ++i) {
            System.out.println("Hello World!");
        }
    }
}
cs


사용자로부터 숫자를 하나 입력 받아 Hello World를 출력하는 예제이다.

시간복잡도를 구할때는 보통 반복되는 부분에 대해서만 계산을 한다.

내가 아는한 이렇게 생각해볼 수 있다.

만약 사용자가 1이라는 숫자를 입력했다라고 하자

그러면 sc객체를 만드는 것부터 몇번을 반복할 것인지 물어보기위해 출력하는 것 등등

적지 않은 비중을 차지할 것이다.


하지만, 우리는 지금 '점근적' 상한에 대해 알아보고 있는 중이라는걸 기억해내자.


만약 사용자가 int의 경계값인 21억 4748만 3647을 입력했다고 하자.

그러면 위에서 언급한 작업이 점근적인 관점에서 보았을 때 수행 시간에 영향을 줄까?

내가 수중에 천원이 있는데 용돈 천원 받는것과, 수중에 21억이 있는데 용돈 천원 받는것의 차이라고 할까?

큰 의미가 없다.

그렇게 때문에 반복되는 작업에 대해서만 고려를 하지 단순 연산에 대해서는 고려하지 않는다.


그렇다고 무조건 반복되는 작업에 대해서 고려되는 것은 아니다.

예를 들어 위의 for문을 for(int i = 0; i < 10; +=i) { ... } 라고 고친다면,

상수시간이 걸린다라고 할 수 있기 때문에

점근적 시간복작도 관점에서 역시 큰 의미를 지니지 않기 때문이다.



그런 의미에서 위의 코드와는 별개로 이런것을 본적이 있을 것이다.

어떤 소스의 반복 시간 f(n) = 2n^3 + 2n^2 + n + 20000 일 때 시간복잡도는 O(n^3) 이다.


최고차항만 남기고 다른 값들은 모두 소거되었다.

n값이 무한대로 커진다라면 최고차항 이외의 것들에 대해서는 점근적으로 무의미하기 때문이다.


갑자기 결론을 짓자면, 이러한 관점에서 위의 Hello World를 출력하는 소스의 시간 복잡도는 O(n) 이라고 할 수 있다.

(for문이 n번 반복하기 때문에)



앞으로 다룰 여러가지 많이 알려져있는 정렬 알고리즘이라던가 최단경로 알고리즘 등을 다룰 때

이 시간 복잡도를 어떻게 계산할 수 있는지에 대해 꾸준히 다뤄볼테니

우선 이런식의 개념이다라고만 우선 정리하려 한다.





그럼 다음으로 공간복잡도에 대해 알아보자.

시간복잡도가 '너 얼마나 걸리니?'의 문제였다면, 이 공간복잡도는 '너 공간을 얼마나 차지하니?'의 문제이다.

이것은 RAM을 얼마나 사용하고 있느냐를 생각할 수 있다.

요즘엔 대용량 컴퓨터가 많아져서 큰 의미를 갖진 않게 되었다고는 한다.


어쨌든 이 공간복잡도라는 것은 작성한 프로그램이 얼마나 많은 공간을 차지하느냐에 대한 것인데,

크게 두 가지로 구분할 수 있다고 한다.


1. 작성한 프로그램을 저장하기 위한 공간, 이 프로그램을 실행시키기 위한 공간 등

2. 어떠한 문제를 해결하기위해 작성한 알고리즘을 수행할 때 필요로 하는 저장공간


느낌이 오겠지만 일반적으로 2번의 경우가 공간복잡도를 계산하는 기준이 된다.



.. 안타깝게도 공간복잡도를 계산하는 정확한 방법에 대해 아직 정확히 찾아내지 못했다.

대부분이 '공간을 얼마나 차지하느냐가 공간복잡도다', '요즘엔 그렇게 중요하지 않다' 가 대부분이다.

추후에 정확한 계산 방법을 찾아내서 수정해야겠다.

직접 발품을 팔아야겠다.





0 Comments