빅오 표기법(Big-O notation), 시간복잡도, 공간복잡도

 

 

구현한 알고리즘의 성능을 보기로만으로 비교하기는 쉽지 않다. 

그렇기에 어느정도의 척도를 갖고 비교해야만하는데 우리는 이러한 문제를 해결하기위해 

빅오 표기법을 사용할 수 있다. 

 

빅오 표기법 이란 알고리즘의 성능을 수학적으로 표현해주는 표기법으로 

O 라는 함수 안에 숫자 혹은 n 을 넣음으로써 알고리즘의 성능을 표기할 수 있다.

여기 성능은 시간과 공간복잡도를 표현한다. 

++ 

알고리즘의 실제 러닝타임을 표기하는 것이 아닌, 데이터나 사용자의 증가량에 따른 알고리즘의 성능을 예측하는 것이

목표이기 때문에 상수가 100인든 11000 이든 O(1)로 표기한다. 또한 O(2n) -> O(n) 으로 볼 수도 있다.

그러나 O(n^2+m) 같이 각 항의 변수가 다를 경우는 함부로 없앨 수 없다.

 

O(1) 알고리즘은 데이터 크기에 상관없이 언제나 일정한 시간을 가지는 알고리즘을 의미한다. 

 

그럼 가볍게 예시로 두겠다. 

O(n) 과  O(n^2) 중 무엇이 더 빠를까? 

 

O(n)

 O(n^2)

n이 증가함에 따라 O(n^2) 의 처리 시간이 증가함으로 O(n)이 빠르다 !

 

그렇다면 O(NM)은 어떻게 할까?

변수가 두개임으로 해당 값의 증가그래프가 O(n^2)에서부터  바뀐다. 

 

계속해서 보면 O함수 안에 n의 제곱에 지수가 상승할 수록 위와 같이

기울기가 time 축에 가파르게 상승함을 예측할 수 있다.

 

즉,  n의 제곱 지수가 상승함은 시간이 오래걸린다는 것으로 쉽게 생각할 수 있다.

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) 

 

그렇다면 1중 반복문을 통해 시간 복잡도를 계산해 보겠다. 

기본적으로 사칙연산의 경우 O(1)처럼 생각해도된다. 

https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

소수 찾기 문제

 

n = int(input())
arr = list(map(int,input().split()))
count = 0
for i in arr:
    if i == 1:
        count +=1
        continue
    for j in range(2,i):
        if i % j ==0 :
            count +=1
            break
print(len(arr) - count)

다음 코드에서 for 문은 n에 의해서 for i in arr에 n번,

for j in range(2,i) 에서 i-2번 

n(i-2) = n*i -2n

가장 큰 값인 O(n*i) 로 본다. 

 

문제에서 N 은 100이하, 

수(i) 는 1000이하의 수 

즉, 최대 천만 근처까지 연산이 필요하다는 것을 짐작할 수 있다. 

컴퓨터가 1초에 가장 간단한 연산을 1억번 정도 계산한다 생각하면 1억번 이내이므로 해당 코드는 시간초과가 뜨지 않는다. (보통 제한이 1초다) 

 

그렇기에 우리가 알고리즘을 구현할 떄  계수를 줄이기위해 노력하기 보다는 차수를 줄이는데 노력하는 것이 옳다

반복문을 사용할 때 다시 한번 적게 사용할 수 없을까 구현한 코드를 지우고 다시 적는 고민하라는게 아니다

처음부터 어떻게 설계를 할지 대략적인 틀을 만들고 코드를 구현하는것이 옳다. 

 

지금까지 시간복잡도로 얘기해왔지만 공간 복잡도 또한 존재한다. 

보통 시간 복잡도를 따라 공간복잡도가 간다. 

그렇다고 공간 복잡도를 무시하라는건 아니지면 현대에 많으 메모리를 갖고 있기 때문에 크게 신경쓰지 않아도 된다.

(하지만... 메모리 할당이 시간을 많이 잡아 먹기 때문에 또한 조심해야한다)

 

 

강의영상)https://www.youtube.com/watch?v=6Iq5iMCVsXA

참고 블로그)https://m.blog.naver.com/PostView.naver?blogId=kks227&logNo=220769859177&navType=by