시간 복잡도, 공간 복잡도

포스팅에 앞서 내용이 틀릴 수 있습니다.

해당 부분 지적 감사히 받습니다.

 

알고리즘에서는 복잡도를 판단하는 2개의 지표가 있다.

첫번째는 시간, 두번째는 공간 복잡도이다.

 

여기서 의미하는 시간과 공간이란 알고리즘이 동작하는 시간,  알고리즘이 돌며 사용되는 메모리의 크기이다.

 

이 두개의 복잡도를 고려하여 가장 효율적인 프로그램, 혹은 문제에서 요구하는 조건에 맞게끔 설계하는 것이 알고리즘 문제의 핵심이다.

 

먼저 시간복잡도에 대해 알아보자.

 

알고리즘에서의 시간복잡도는 Big-O 표기법을 통해 계산한다.

 

Big-O 표기법이란?

알고리즘이 돌아가는데 필요한 가장 큰 차수로만 나타낸다.

 

특징

 

1. 상수항은 버린다. O(n+5) -> O(n)

 

2. 계수 또한 버린다. O(2n) -> O(n)

 

3. 최고 차항만을 표시한다.  O(2n^2 +5n+5) -> O(n^2)

 

알고리즘의 시간 복잡도를 계산하기 위해, 반복횟수 n에 대해 가장 큰 영향을 주는 항 남기고 모두 버리는 방식이다.

 

시간복잡도의 오름차순은 어떻게 될까?

 

O(1) < O(log_n) < O(n) < O(nlog_n) < O(n2) < O(2^n) < O(n!) 순으로 복잡해진다.

 

그렇다면, 시간복잡도는 어떻게 계산할까?

 

계산의 방법에 앞서 Big-O 표기법의 중요한 것들을 알고가자.

 

시간 복잡도를 계산할 때는, 연산의 수 만 고려한다.

 

상한선을 값으로 쓴다.

 

O(1) 부터 순서대로 알아보자.

 

O(1)

a = 1

b = 2

print(a+b)

연산 a = 1, b = 2, a + b이 수행되므로 O(3)의 시간복잡도를 가지게 된다.

하지만 상수의 경우 무시된다.

 

O(N)

a = 0

for i in range(1,n+1):

    a += i

a=0 , i = 1 ~ n + 1, a += i, 1+n+1+ n = 2n+2의 시간복잡도를 갖게 된다.

따라서 시간 복잡도는 O(N) 이 된다.

 

O(N^2)

a = 0

for i in range(1,n+1):

    for j in range(1,n+1):

        a += 1

a = 0, i  = 1 ~ n+1, j  = 1 ~ n+1, a += 1,   n^2 + 2n + 3 의 시간 복잡도를 갖게 된다.

따라서 시간 복잡도는  O(N^2) 가 된다.

 

알고리즘 문제에서는 시간제한이 주어진다.

 

보통 10^8, 즉 1억번의 연산이 수행될 때, 약 1초가 흐른다는 사실을 알고있으면 앞으로 알고리즘을 설계할 때, 시간복잡도를 고려하여 문제를 풀 수 있게된다.

 

추가 : 파이썬은 1초에 약 2000만번의 연산을 수행한다고 한다.

 

또한 알고리즘 문제를 풀 때는, n log_n의 시간복잡도를 넘으면 안되는것 같다.

 

찾아보니, O(log n)의 연산은 2진 탐색 기법의 경우를 이야기 하는것 같은데, 추후에 해당 포스팅에

log n과 n, log n, 2^n, n!의 시간복잡도가 나올 수 있는 경우를 추가하겠다.

 

파이썬에서 시간을 계산하고 싶으면

import time

start_time = time.time()

end_time = time .time()

start_time을 알고리즘 시간 측정을 시작할 부분에 입력하고,

end_time을 알고리즘의 시간 측정을 종료할 부분에 입력한다.

 

최종적으로

print(end_time-start_time)

형식으로 출력하면 걸린 시간 값을 측정할 수 있다.

 

또한 각 시간 복잡도에 따른 정렬 알고리즘을 알아보자.

O(1)

스택의 push, pop

 

O(log n)

이진트리

 

O(n)

for문

 

O(n log n)

퀵 정렬, 병합 정렬, 힙정렬

 

O(n^2)

이중 for문, 삽입 정렬, 버블 정렬, 선택 정렬

 

O(2^n)

피보나치 수열

 

 

공간 복잡도

 

공간 복잡도란, 프로그램을 실행시킨 후 완료되는데까지 필요한 공간의 양을 뜻한다.

 

공간복잡도를 표기할 때도 Big-O 표기법을 사용한다.

 

시간 복잡도는 1초, 0.5초 같이 초를 기준으로 조건을 제시한다.

 

공간 복잡도에서는 128mb, 256mb등과 같이 mb를 기준으로 제시해준다.

 

보통의 코딩테스트 에서는 128mb에서 512mb까지를 조건으로 제시해준다고 한다.

 

공간 복잡도는 식이 있다.

 

S(P)=c+Sp(n)

 

공간 복잡도 = 고정 공간 + 가변 공간

 

고정 공간과 가변 공간에 대해 알아보자.

 

고정 공간 : 알고리즘과 무관한 공간.

가변 공간 : 알고리즘이 실행됨에 따라 필요한 공간.

 

예를 들면 고정 공간에는, 코드 저장공간, 단순 변수 및 상수 저장공간이 있다.

 

가변 공간은 실행 중 동적으로 필요한 공간이다.

 

int의 경우 리스트의 길이가 1,000,000 일 때, 약 4mb

32,000,000 일 때 128mb 64,000,000 일 때, 256mb  128,000,000일 때 512mb를 차지한다.

 

 

출처 : https://xodud2972.tistory.com/60

Python 51 - 시간복잡도, 공간복잡도, 빅오표기법 ( 알고리즘 공부 )

배운 점

1. 간단하게 시간복잡도에 대해 계산할 수 있는 방법을 배웠다.

2. 새벽은 빠르다.