[Algorithm] 시간 복잡도란? 공간 복잡도란? 빅 오 표기법이란?

알고리즘 종류를 검색하다 보면 가장 먼저 설명하는 개념이 빅 오 표기법이란 것이다.

이번 포스팅에선 빅 오 표기법이란 게 뭔지 정리한다.

 

빅 오 표기법에 대해 알기 전에 먼저 시간 복잡도, 공간 복잡도라는 말이 뭘 뜻하는 건지 알아야 한다. 왜냐면 시간 복잡도를 표기하는 방법 중 하나가 빅 오 표기법이기 때문이다.

 

https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84

시간 복잡도 - 위키백과, 우리 모두의 백과사전

시간 복잡도는 문제 해결에 걸리는 시간, 입력의 함수 관계를 가리킨다. 컴퓨터 과학에서 알고리즘의 시간 복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다. 알고리즘의 시간 복잡도는 주로 빅 오 표기법을 써서 나타내며 이 빅 오 표기법은 계수와 낮은 차수의 항을 제외시키는 방법이다. 이런 방식으로 표현할 때(예를 들면 입력 크기를 무한대로 입력해서) 시간 복잡도를 점근적으로 묘사한다고 말한다. 예시로서 만약 크기 n의 모든 입력에 대한 알고리즘에 필요한 시간이 최대 5n^3 + 3n의 식을 가진다면 이 알고리즘의 점근적 시간 복잡도는 O(n^3)이라고 할 수 있다.
시간 복잡도는 기본 연산을 수행하는 데에 어떤 고정된 시간이 걸릴 때 알고리즘에 의해서 수행되는 기본 연산의 개수를 세어 예측할 수 있다. 그러므로 걸리는 시간의 총량, 알고리즘에 의해 수행되는 기본적인 연산의 개수는 최대 상수 인자만큼 다르다. 알고리즘의 수행 시간은 동일 크기의 다양한 입력에 의해 달라질 수 있기 때문에 가장 많이 쓰이는 최악의 시간 복잡도의 알고리즘 시간을 T(n)이라 했을 때 이것은 크기 n의 모든 입력에 대해 걸리는 최대 시간으로 정의할 수 있다...(중략)

 

https://en.wikipedia.org/wiki/Time_complexity

Time complexity - Wikipedia

시간 복잡도는 알고리즘을 실행하는 데 걸리는 컴퓨터 시간의 양을 설명하는 계산 복잡도다. 시간 복잡도는 일반적으로 각 연산을 수행하는 데 고정된 시간이 걸린다고 가정하고 알고리즘에 의해 수행되는 기본 연산의 수를 세어 추정한다. 따라서 알고리즘에 의해 수행되는 기본 연산의 수와 소요 시간은 상수 인자에 의해 관련되는 것으로 간주된다. 알고리즘의 실행 시간은 동일한 다른 입력 간에 다를 수 있으므로 일반적으로 주어진 크기의 입력에 필요한 최대 시간인 최악의 시간 복잡도를 고려한다. 덜 일반적이고 일반적으로 명시적으로 지정되는 평균 케이스 복잡성은 주어진 크기의 입력에 소요된 시간의 평균이다. 두 경우 모두 시간 복잡도는 일반적으로 입력 크기의 함수로 표현된다. 이 함수는 일반적으로 정확하게 계산하기 어렵고 작은 입력에 대한 실행 시간은 일반적으로 결과적이지 않기 때문에 중점을 둔다. 입력 크기가 증가할 때 복잡성의 동작, 즉 복잡성의 점근적 동작에 대해 설명한다. 따라서 시간 복잡도는 일반적으로 빅 오 표기법으로 표현된다. 여기서 n은 입력을 나타내는 데 필요한 비트 단위의 크기다
알고리즘 복잡도는 빅 오 표기법에 나타나는 함수 유형에 따라 분류된다. 예를 들어 시간 복잡도가 O(n)인 알고리즘은 선형 시간 알고리즘이고 a > 1에 대해 시간 복잡도가 O(n^a)인 알고리즘은 다항식 시간 알고리즘이다

 

알고리즘을 함수 형태로 만들었다고 가정했을 때 이 함수의 매개변수와 함수 완료까지 얼마나 걸리는지에 대한 관계를 다루는 개념이라고 생각된다.

다른 사람들은 시간 복잡도를 어떻게 설명하는지 확인해 봤다.

 

https://coding-factory.tistory.com/608

[Algorithm] 알고리즘 시간복잡도에 대하여

시간 복잡도란 특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간을 의미한다. 같은 결과를 가져오는 코드도 어떻게 쓰냐에 따라 걸리는 시간이 달라질 수 있다. 같은 결과를 나타내는 코드라면 최대한 시간이 적게 걸리는 게 좋은 코드다. 그렇기에 더 효율적인 알고리즘을 구성하기 위해서 시간 복잡도의 측면을 고려하고 중요하게 본다. 특히 최근 알고리즘 문제 해결에서 대부분 실행시간을 정해놓고 그 시간 안에 코드가 돌아가야 정답으로 체크하기에 시간 복잡도의 중요성이 더더욱 커졌다고 볼 수 있다.

 

즉 알고리즘을 실행해서 끝나기까지 얼마 걸리냐가 시간 복잡도란 것 같다.

그럼 공간 복잡도는 뭘 뜻하는 건가?

 

https://coding-factory.tistory.com/609

[Algorithm] 알고리즘 공간복잡도에 대하여

공간 복잡도는 프로그램 성능 분석 방법 중 하나로 프로그램이 얼마나 많은 공간(메모리)를 차지하는지 분석하는 방법이다. 최근엔 컴퓨터 성능 발달로 메모리 여유 공간이 넘치기 때문에 중요성은 예전에 비해 많이 낮아졌다. 최근에는 공간 복잡도 보다는 시간 복잡도를 우선시해서 프로그램을 작성한다

 

요즘 컴퓨터 램이 수십 기가바이트고 SSD, HDD 용량은 테라바이트인 시대에 프로그램이 얼마나 많은 메모리를 차지하는지 분석하는 건 확실히 덜 중요할 것 같긴 하다. 심지어 핸드폰 또한 저장용량은 작정하고 프로그램을 설치해대지 않는 이상 엄청나게 여유롭다.

 

---

 

그럼 빅 오 표기법은 무엇인지 확인해본다.

 

https://en.wikipedia.org/wiki/Big_O_notation

Big O notation - Wikipedia

빅 오 표기법은 인수가 특정 값이나 무한대로 향하는 경향이 있을 때 함수의 제한 동작을 설명하는 수학적 표기법이다. 빅 오는 Paul Bachman, Edmund Landau 등이 발명한 표기법 계열의 구성원으로, 집합적으로 Bachman-Landau 표기법 또는 점근 표기법이라고 한다...(중략)...컴퓨터 과학에서 빅 오 표기법은 입력 크기가 커짐에 따라 실행 시간 또는 공간 요구 사항이 어떻게 증가하는지에 따라 알고리즘을 분류하는 데 사용된다...(중략)

 

https://www.linkedin.com/pulse/big-o-notation-simple-explanation-examples-pamela-lovett/

Big-O Notation: A simple explanation with examples

빅 오 표기법은 알고리즘이 실행되는 데 걸리는 시간(시간 복잡도) 또는 알고리즘이 사용하는 메모리의 양(공간 복잡도)를 설명하는 데 쓰이는 언어다. 빅 오 표기법은 알고리즘의 최고, 최악, 평균 실행 시간을 표현할 수 있다. 소프트웨어 엔지니어로서 빅 오에 대한 대부분의 논의는 알고리즘의 "상한" 실행 시간에 초점을 맞추고 있으며 이는 종종 최악의 경우라고 한다. 주목해야 할 중요한 부분은 빅 오 표기법을 사용할 때 실행 시간이 초, 밀리초, 마이크로초 등과 직접적으로 동일하지 않다는 것이다. 실행 시간 분석은 프로세서, 언어 또는 실행 시간 환경 같은 특정 사항을 고려하지 않는다. 대신 크기 n의 문제를 완료하는 데 걸리는 작업 또는 단계의 수로 시간을 생각할 수 있다. 즉 빅 오 표기법은 입력 크기에 비해 런타임이 얼마나 빨리 증가하는지 추적하는 방법이다

 

알고리즘(=코드)이 실행되는 시간이 아니라 입력값을 어떤 걸 넣었느냐에 따른 알고리즘의 성능을 표시하는 방법 정도로 생각하기로 했다. 다른 곳에서 설명하는 걸 봐도 거기서 거기다.

 

다음은 빅 오 표기법의 종류다.

 

형태	의미
O(1)	상수 시간
O(log N)	로그 시간
O(N)	선형 시간
O(N^n)	n차 시간(2차 시간, 3차 시간, ...)
O(2^n)	지수 시간

 

위의 빅 오 표기법들의 시간 순서는 아래와 같다. 왼쪽으로 갈수록 제일 빠르고 오른쪽으로 갈수록 제일 느리다.

 

O(1) > O(log N) > O(N) > O(N^n) > O(2^n)

 

먼저 가장 빠른 O(1)은 입력값이 증가하더라도 소요 시간이 늘어나지 않는다는 걸 의미한다.

 

def sayHello(x):
    print("Hello!")


sayHello(100)

 

함수에 100을 넣건 100억을 넣건 function()은 "Hello!"만 출력한다. 입력값에 상관없이 즉시 값을 얻을 수 있어서 가장 빠른 시간 복잡도를 가진 코드다.

 

O(log N)의 시간 복잡도를 갖는 코드 예시는 아래와 같다.

 

import math


num = 4

while math.floor(num) > 0:
    num = num / 2

print(num)

 

원하는 값을 찾을 때마다 찾는 범위가 절반씩 사라지기 때문에 O(1) 다음으로 가장 빠른 실행 속도를 낸다.

절반씩 탐색 범위를 줄이는 것은 이진 탐색에서 사용하는데 이것에 대한 내용은 추후 포스팅한다.

 

 

O(n)의 시간 복잡도를 갖는 코드 예시는 아래와 같다.

 

def runFor(n) :
    for i in range(n):
        print(str(i) + "번 Hello!")


def runFor2(n):
    for i in range(2 * n):
        print(str(i) + "번 Hello!")


runFor(10)
runFor2(10)

 

입력값이 증가함에 따라 for문이 도는 횟수가 늘어난다. runFor()의 경우 2를 넣으면 for문이 2번 돌고 10을 넣으면 10번 돌 것이다. runFor2()도 도는 횟수만 다를 뿐 입력값이 커짐에 따라 실행시간이 늘어나는 건 똑같다.

빅 오 표기법에선 2n, 3n 등의 실행 시간이 있을 때 앞의 계수를 무시하기 때문에 n의 앞에 100이 붙든 100억이 붙든 결국 O(n)이다.

 

 

O(N^n)의 시간 복잡도를 갖는 코드 예시는 아래와 같다.

 

def forTest(n):
    for i in range(n):
        for j in range(n):
            pass


forTest(100)

 

반복문을 2중, 3중으로 만들 경우 입력값이 증가함에 따라 시간이 n^2, n^3 식으로 증가한다.

1을 넣으면 1초가 걸리지만 10을 넣으면 100초가 걸리고 100을 넣으면 1000초가 걸린다. 이 경우도 마찬가지로 계수가 무엇이든 O(N^n)이라고 표기한다.

 

 

O(2^n)의 시간 복잡도를 갖는 코드 예시는 아래와 같다.

 

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)


print(fibonacci(10))

 

이런 시간 복잡도를 갖는 대표적인 알고리즘이 피보나치 수열을 재귀로 구현한 코드다.

10을 넣으면 55라고 금방 답을 주지만 100을 입력하면 시간이 매우 오래 걸리게 된다.

 

 

마지막으로 O(N), O(log N) 이라고 표기하는데 저 N이 붙는 기준은 무엇인가 이해가 안되서 찾아봤다.

위에서 썼던 코드를 다시 가져온다.

 

def forTest(n):
    for i in range(n):
        for j in range(n):
            pass


forTest(100)

 

여기서 2중 for문이 있는데 1을 넣으면 i, j는 모두 1번씩 실행되지만 2를 넣을 경우 i, j는 2번씩 실행되어 결국 forTest(n)은 내부적으로 4번 반복한 다음 결과값을 내놓을 것이다.

그래서 실행 횟수를 N이라고 하면 이 코드의 빅 오는 O(N^2)가 되는 것이다. 3중 for문이라 해도 마찬가지로 O(N^3)이 되는 것이다.

그렇다면 중첩 반복문이 아니라 for문이 따로 떨어져 있다면 어떨까?

 

def test(n):
    for i in range(n):
        print("1")

    for i in range(n):
        print("2")

 

앞에서 for문은 1번 돌 때마다 실행 횟수를 N이라고 가정한다고 했다. 그런데 여기선 N이 2개니까 N+N이 되어 2N이 될 것이다.

그리고 빅 오 표기법의 규칙에 따라 계수인 2는 지워지고 결국 O(N)이 될 것이다.

또한 2중 반복문을 실행하지만 함수 매개변수가 2개라서 바깥 for문에선 1번 매개변수, 내부 for문에선 2번 매개변수를 사용하는 경우도 있다.

 

def test(n, m):
    for i in range(n):
        for j in range(m):
            pass

 

이 경우에는 N, M이 무슨 숫자냐에 따라 각 반복문이 실행되는 횟수가 달라지기 때문에 이런 코드의 시간 복잡도는 O(N*M)이다.

 

for문이 아니라 if문이 들어가거나 리스트 요소 등 메모리에 접근하는 경우도 있다. 이 경우엔 +1로 간주해서 2N+3이 되는 경우도 있는데 이 경우에도 계수와 뒤의 +3은 지워져서 O(N)이 된다.