시간복잡도 공간복잡도 - siganbogjabdo gong-ganbogjabdo

좋은 알고리즘이란 무엇일까? 당연히 작은 메모리 공간을 차지하면서 적은 시간 내에 주어진 임무를 제대로 수행하는 알고리즘이 좋은 알고리즘이다. 알고리즘을 평가할 때 수행시간과 메모리 사용량을 평가기준으로 두는데, 이 각각에 해당하는 사항이 시간 복잡도 (time complexity) 와 공간 복잡도 (space complexity) 이다.

시간 복잡도란, 알고리즘의 수행시간의 분석 결과이며, 공간 복잡도란 알고리즘의 메모리 사용량에 대한 분석 결과이다.

시간 복잡도의 계산

알고리즘의 시간 복잡도는 연산의 횟수를 세고 처리해야 할 데이터의 수 n에 대한 연산횟수의 함수 T(n) 을 만들어서 계산한다.

연산 횟수의 카운팅에는 3가지 경우가 있다.

1. 최선의 경우 (Best Case)
2. 최악의 경우 (Worst Case)
3. 평균적인 경우 (Average Case)

알고리즘이 복잡해질 수록 평균적 경우는 구하기 어려워진다. 따라서 보통 알고리즘의 성능은 최악의 경우로 파악한다.

Elementary Operation

Program Step에서 Elementary Operation이란 프로그램의 진행 정도를 나타내는 기본 단위이다. Elementary Operation에는 4 가지 종류가 있다.

1. 대입연산
2. 사칙연산 (덧셈, 뺄셈, 곱셈, 나눗셈)
3. 비교구문
4. 함수 호출

알고리즘의 실행 순서를 따라가며 Elementary Operation이 일어나는 수를 측정해 보자.

def sum(num_list, n):
    tempSum = 0 # 대입 연산

    for num in num_list: # num_list의 수 (n번 만큼 반복)
        tempSum += num # 사칙 연산
    
    return tempSum

print(sum([1,2,3,4,5], 5))

위와 같은 함수가 있다고 가정해보자. 함수가 호출되면, tempSum이라는 변수에 대입 연산이 한번 일어난다 (1). 그 후, num_list를 돌아가며 num_list의 길이 (즉, n) 만큼 사칙 연산이 반복된다 (n) 따라서, 위 함수의 시간 복잡도는 n+1 이다.

성능 비교

여기 두 프로그램이 있다고 하자. 프로그램 1의 성능은 n^2 + n이고, 프로그램 2의 성능은 20n이다. n의 크기가 작을 경우, 프로그램 1의 성능이 더 좋을 것이다. 그러나 n의 크기가 커지면 커질 수록, 프로그램 1의 처리 시간은 프로그램 2에 비해 훨씬 길어진다. 따라서 각 프로그램들의 성능은 n의 크기에 따라 결정되기도 한다.

그러나 처리해야할 데이터의 수 (n) 이 적다면, 두 프로그램 모두 좋은 성능을 낼 것이며, 별로 차이가 없을 것이다. 따라서 이 경우 문제될 것이 없다. 그러므로, n이 큰 경우의 처리가 중요하다.

Big O 표기법 (Big O Notation)

Big O란 연산 횟수의 함수 T(n) 의 최고차항의 차수에 O를 씌운 표기법이다. 아래와 같이 표기하면 된다.

빅오의 순서는 아래와 같으며, 커질 수록 연산 횟수가 더 많다는 뜻이며, 연산에 더 오랜 시간이 걸린다는 뜻이다. 화공과에서 수학을 배울 때 배우던 내용과 비슷하다.

위 표는 각 빅오에 따라서 연산 횟수가 얼마나 차이날 수 있는지 보여준다.

공간 복잡도

공간 복잡도 계산은 간단하다. 메모리를 얼마나 사용했는지 계산하면 된다. 공간 복잡도 역시 시간 복잡도 처럼 보통 최악의 경우 (worst case) 를 따져 빅오 노테이션으로 그 복잡도를 판단하게 된다.

가령 크기가 n인 배열을 입력했는데, 알고리즘이 내부에서 n * n 의 이차원 배열을 생성한다면 이 알고리즘의 공간 복잡도는 n^2 가 된다.

공간 복잡도는 보통 시간 복잡도보다 중요하게 생각되지 않는 경우가 많다. 그러나 빅데이터 처리를 하는 경우, 공간 복잡도가 위와 같이 커지게 된다면, 메모리에 한 번에 올라가지 않아 프로그램을 실행할 수 없는 문제가 발생할 수 있다. 이 경우, 데이터를 나눠서 처리하고 다시 합치는 방법을 사용하게 된다.

알고리즘 작성 시, 공간 복잡도를 아예 생각하지 않으면 위험할 수 있다. 따라서 공간 복잡도도 신경써서 작성해 주자.

출처

http://ledgku.tistory.com/33

https://feel5ny.github.io/2017/12/09/CS_01/

https://wayhome25.github.io/cs/2017/04/20/cs-26-bigO/

빅오 표기법이란?

알고리즘의 효율도를 측정하는 척도이다. 해당 알고리즘이 시간적으로 얼마나 소요되는지, 그리고 공간적으로 어느정도를 차지하는지를 알려주며, 이를 통해 알고리즘의 효율성을 파악할 수 있다. 빅오 즉, 알고리즘의 효율도를 측정하기 위한 척도는 크게 "시간복잡도"와 "공간복잡도"로 나눌 수 있다.

공간복잡도란?

공간복잡도는 안어 그대로, 프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원 공간의 양을 말한다. 여기서 자원공간이라 하면, 메모리(RAM)인 것이다. 즉 해당 알고리즘을 해결하기 위해 실제로 사용되는 메모리의 양으로 효율도를 측정하는 것이고, 당연하겠지만 적게 사용될 수록 효율적임을 의미한다.

그렇다면 공간복잡도는 어떻게 계산할 수 있을까?
공간복잡도는 코드 작성 시에 선언된 변수들과 관련이 있다. 단순 변수 혹은, 고정적으로 정의된 변수는 고정공간을 차지한다. 해결하려는 문제의 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들을 위해서 필요로 하는 공간, 그러니까 예를 들어 함수선언에 사용된 인자들, for문을 위한 가상의 변수들(i나 n같은)이 차지하는 공간은 가변 공간이다. 공간 복잡도는 이러한 고정공간과 가변공간의 합인 것이다.

이를 예시를 통해 살펴 보고자 한다.

a, b, c는 3개의 변수로 메모리상 1씩 3개해서 3을 차지하는 것처럼 보일 수 있지만, 외부에서 인자로 받아오고 함수는 바로 리턴하기 때문에 공간 복잡도는 0이다. 따라서 공간 복잡도는 O(1)이라고 볼 수 있다.

위 예에서는 우선 변수 s를 초기화하는 1, 그리고 i를 초기화하는 1, 그리고 for문을 끝내기 위한 n값 1, 끝으로 반복문에서 arr[i]의 n값을 해서 총 공간 복잡도는 n + 3 이 될 것이다.. 빅오 표기법으로는 O(n) 일 듯.

아마도 val 이라는 변수를 초기화 하는데 1, 그리고 반복문에 사용된 변수 i에 1. 그래서 반복문이 몇번 반복되는 것과 상관 없이 공간 복잡도는 2가 되고 빅오 표기법으로는 O(1)이 될 듯.

시간복잡도란?

시간 복잡도는 공간 복잡도보다는 좀 더 이해하기 쉬웠다. (개념이 쉽다기 보다는 일반적으로 빅오 표기법과 시간 복잡도가 거의 한쌍처럼 같은 개념으로 같이 묶여서 많이 설명되고 사용되다보니 좀 더 익숙한 듯 하다.) 공간 복잡도가 공간의 사용에 따른 효율성을 본다면 시간 복잡도는 말 그대로 시간적인 효율성을 측정하는 것이다. 여기서 더 구체적으로 설명하자면, "시간적으로 얼마나 소요되는지"는 우리가 알고 있는 그 시간적인 개념이라기 보다는 "어떠한 알고리즘을 해결하기 위한 단계 수"이다. 그리고 보통 해당 알고리즘을 해결하기 위한 가장 최악의 단계 수를 시간복잡도로 본다. 효율성의 측면에서 성능의 순서는 상단의 그래프 이미지를 참고 하면 된다. 즉 시간 복잡도를 그래프로 표기했을 때, 가파를수록 비효율적이라는 의미이다. (해당 그래프는 공간 복잡도에도 해당되는 의미인 듯하다. 계산하는 방법은 다르지만,
결국 공간 복잡도도 빅오 표기법으로 표기 될 것이기 때문이다.)

대표적인 빅오 표기법들

O(1)

여기서 1은 숫자 1을 나타내기 보단 상수를 의미한다. 입력되는 데이터의 량과 상관없이 일정한 횟수로 실행 되거나 한 단계만을 거치는 것을 말한다. 시간이 얼마나 걸리든 한 단계만 거치면 O(1)의 복잡도를 가진다. 대표적으로 배열 끝의 삽입과 삭제의 시간복잡도가 O(1)이다.
a. 자료 구조 내의 데이터 수가 3개인 경우, 데이터 가장 앞의 요소 반환: 1번의 연산
b. 자료 구조 내의 데이터 수가 6개인 경우, 데이터 가장 앞의 요소 반환: 1번의 연산
c. 자료 구조 내의 데이터 수가 9개인 경우, 데이터 가장 앞의 요소 반환: 1번의 연산
데이터 수의 증감여부와 상관없이 연산과정은 항상 동일하다.

O(logn)

데이터의 증가량에 따라 연산 수나 단계가 늘어나지만 그 양이 n보다는 적다. 가령 n이 증가함에 따라 일정하게 시간복잡도도 비례해서 늘어나는 것이 아니라, 데이터가 n씩 증가함에 따라 시간복잡도도 증가하지만, 그 증가량에 비해 복잡도가 증가하는 양은 적다. 그러다 점차 O(1)에 가까워진다.

n 의 크기를 반씩 줄이는 걸 가정
n 이 반씩 줄다보면 k 단계에서 최종적으로 1이 된다 가정하자.
단계별로 n → n/2 → n/4 → n/2의k 승 진행
n = 2 의 k 승
양쪽에 로그 붙이면 logN = k 가 됨.
예시 : n = 16 이라 가정하면, 16 → 8 → 4 → 2 → 1 이고, 이는 logN 의 시간복잡도를 가지게 됨. 실행 횟수는 log(16) = 4 가 된다.

O(n)

데이터의 양에 따라 정비례하게 증가한다. 대표적으로 반복문을 한번 돌릴때 O(n)의 시간복잡도를 보인다.

O(nlogn)

O(n)보다는 많이 실행 되지만 O(n2)보다는 적게 실행되는 그 사이??라고 생각하면 좀 더 쉬울듯?

O(n2)

데이터에 양에 따라 걸리는 시간이 제곱에 비례하는 것을 말한다. n번 반복되는 반복문이 2번 중첩될 때를 생각하면 쉬울 것 같다.