Big-O 표기법 정리

결과는 같은데, 과정은 다르며, 이에 따른 여러가지 알고리즘이 있다.

 

이처럼 다양한 알고리즘도 성능이 제 각각이다.

 

그렇기 때문에 좋은 성능의 알고리즘을 고르는 것이 굉장히 중요하다.

 

가장 좋은 알고리즘을 고르기 위해서는 알고리즘의 효율성을 따지는 데 이 때 두 가지로 나눌 수 있다.

 

시간적 효율성 (얼마나 이 알고리즘이 빠른가) / 공간적 효율성(메모리를 얼마나 차지하는가)

 

=> 얼마나 빠른 시간으로 처리하는가 ('시간 복잡도') / 얼마나 메모리를 차지하는가 ('공간 복잡도')

 

알고리즘의 속도에 영향을 주는 요소는 굉장히 많지만, 제일 영향을 많이 주는 것은 '입력이 n일 때 연산 횟수' 이다.

 

예를 들어, 1~100 까지 순서대로 더하는 프로그램과 1~1000까지 순서대로 더하는 프로그램을 만들었다.

당연히 1~100까지 더하는 프로그램이 더 빠를 것이다.

 

같은 알고리즘이더라도 입력 데이터의 크기에 따라서 수행시간이 달라질 수 있다.

 

그렇기 때문에 알고리즘을 비교할 때, 똑같이 N개의 입력을 가정하고 성능을 알아봐야한다.

 

이런 관점에서 Big O 가 등장했다.

 

시간복잡도 

: 시간X , 조작(연산)되는 횟수 (시간복잡도는 밑에서 많이 다룰 것이다.)

 

공간복잡도

 

알고리즘을 실행하여 종료할 때까지 필요한 기억장치의 크기

*S(P) = c + Sp(n)*

 

알고리즘을 처리하는데 필요한 총 공간은 고정공간과 가변공간의 합으로 이루어진다.

 

- 고정 공간 : 코드 저장, 단순 변수 및 상수를 저장하는 공간

- 가변 공간 : 알고리즘 실행 과정에 동적으로 필요한 공간

 

public int fn_sum(int a[], int n){ // result, n, a[]의 주소값, a[0] ~ a[n-1] 저장 공간
    int result =0;          
    for(int i=0; i<n ; i++){
        result += a[i];
    }
    return result;
}

해당 JAVA 코드를 예시로 보면

fn_sum 이라는 함수 및 알고리즘을 실행하는데 있어서, 

 

고정공간 : result 라는 단순 변수

가변공간 : a[0]~a[1]이라는 heap memory에 저장된다.

 

 

 

📌빅오(Big-O) 표기법

 

빅오가 무엇일까? 알고리즘의 성능을 수학적으로 표현하는 방식이다.

이를 통해서, 알고리즘의 시간복잡도와 공간복잡도(Time Complexity & Space Complexity)를 측정할 수 있다.

또한, 빅오 표기법은 알고리즘의 성능을 측정하는 것이다.

 

처리 시간의 증가율을 알기 위해서 사용하는 것이 바로 "빅오 표기법"이다.

 

Big O  비교 그래프

이중에서도 좀 더 효율적인 시간복잡도로 구성된 코드를 작성하기 위해서 노력해야한다.

 

⚙️ O(1) : 입력한 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘

O(1) 알고리즘

첫번째 배열의 값이 0인지 확인하는 함수이다.

언제나 일정한 속도를 가지고서 함수를 처리하는 알고리즘이다.

 

O(1) 알고리즘

O(1) 알고리즘은 데이터(data)가 증가해도, 처리속도(time)에는 변함이 없는 알고리즘이다.

 

⚙️ O(n) : 입력 데이터 크기에 비례해서 처리되는 시간이 증가하는 알고리즘

O(n) 알고리즘

n 개의 데이터를 받으면 n 이 늘어날 떄마다 처리시간이 걸리는 함수이다.

 

O(n) 알고리즘

data 의 갯수가 늘어남에 따라서 time 또한 비례해서 늘어나는 것이 바로 O(n) 알고리즘이다.

 

언제나 데이터와 시간이 같은 비율로 증가한다.

 

⚙️ O(n²)

O(n²)

 

n을 돌리면서, 그 안에서 n 으로 또 루프를 돌릴 때 해당한다.

 

O(n)

O(n²)

n이 하나 늘어날 때마다, 커지면 커질수록 더 심하게 시간이 늘어나게 된다.

 

O(n²)

 

⚙️ O(nm)

O(nm)

for 문안에 for문으로 되어있는것을 보고서  O(n²) 으로 생각할 수 있지만,

n은 엄청 크고 m은 엄청 작을 수도 있기 때문에, 변수가 다르면 반드시 다르게 표시해줘야한다.

 

O(nm)

O(nm) 그래프

O(nm)의 그래프 역시, 데이터가 증가함에따라 속도가 수직상승하는 구조의 그래프를 보인다.

 

⚙️ O(n³)

O(n³)

 

n의 제곱에 n을 한 번더 돌리는 것이다.

for 문을 3중으로 돌리면 O(n³)이 되는 것이다.

 

O(n) 일 때는 직선

O(n²) 일 때는 면적

O(n³) 일 때는 큐빅이 된다.

 

O(n³) 그래프

데이터가 늘어날 때마다 데이터의 가로 세로 높이 까지 늘어나기 때문에 굉장히 시간이 증가하게 된다.

 

⚙️ O(2ⁿ)

O(2ⁿ) 과 O(n²) 은 굉장히 비슷하게 생겼지만, 다른 알고리즘이다.

O(2ⁿ) 에 대표적인 예로는 피보나치 수열이 있다.

 

피보나치 수열

O(2ⁿ)의 대표적인 예시. 피보나치 수열

 

피보나치 수열의 코드를 재귀함수를 사용해서 구현한 코드이다.

피보나치 수열 구현 코드

함수를 호출 할때마다 함수의 전 숫자와 전전 숫자를 넣어서 호출한다.

매번 함수를 호출할 때마다 2번씩 호출하는데, 이를 트리의 높이만큼 반복하는 것이다.

 

O(2ⁿ)의 대표적인 예시. 피보나치 수열

O(2ⁿ) 의 그래프

다른 알고리즘보다도 데이터의 증가에 따라서 처리시간이 기하급수적으로 늘어난다.

 

번외로 m개씩 n번 늘어나는 알고리즘을 O(mⁿ) 이라고 부른다.

 

 

⚙️ O(log(n))

O(log(n)) 의 대표적인 예시로는 '이진 검색'이 있다.

 

O(log(n)) 의 예시. binary search.

1~9 까지의 배열에서 6을 찾아보자.

 

① 이진검색을 하려면 가운데 값을 찾아서 key값과 비교한다.

② key 값이 더 크기 때문에 (key > 5) 왼쪽 값은 무시하고 오른쪽 값만 보면 된다.

③ 나머지 오른쪽 6~9 중에서 중간값으로 7을 지정한다. key 값이 더 작기 때문에 앞쪽에 있는 것이다.

④ 뒤쪽 값들은 무시하고 앞쪽 값만 보면 되기 때문에 6을 찾을 수 있다.

 

한 번 처리를 할 때마다 검색해야하는 데이터의 양이 절반씩 떨어지는 함수를 O(log(n)) 이라고 부른다.

 

이를 구현한 코드이다.

 

 

k -> key 값
arr -> 배열
s -> 처음 시작 값
e -> 끝 값

m = (s+e) / 2 

=> 시작값과 끝값을 더하고 2로 나눈 "중간값"을 구한다.

if(arr[m] == k) return m;

=> arr[m].  arr 배열의 중간값이 key값과 같다면 m을 반환한다.

else if(arr[m] > k) return F(k,arr,s,m-1);

=> arr[m].  arr 배열의 중간값이 key값보다 크다면, 다시 함수를 호출하고 끝 값을 m-1로 수정한다.

else return F(k,arr,m+1,e);

=> arr[m]. arr 배열의 중간값이 key 값보다 작다면, 다시 함수를 호출하고 시작 값을 m+1로 수정한다.

O(log(n)) 의 그래프

평균적인 O(n)보다도 훨씬 적게 들고, 데이터가 증가해도 성능이 크게 차이가 나지 않는다.

 

⚙️ O(Sqrt(n))

O(Sqrt(n))

n 개를 정사각형으로 채운 후 제일 위에 있는 줄이 바로 제곱근이다.

 

 

⭐️ Big-O 에서 제일 중요한 점

빅오에서는 상수를 과감하게 버린다.

 

O(2n) => O(n)

해당 코드는 시간복잡도가 n만큼씩 2번 돌리기에, O(2n)이다.

하지만 빅오 표기법에서는 O(2n) => O(n) 으로 표시한다.

 

왜냐하면, 빅오 표기법은 실제 알고리즘의 러닝타임을 재기 위해서 만든 것이 아니라, 장기적으로 데이터가 증가함에따른 처리시간의 증가율을 측정하기 위해서 만든 것이다.

상수는 고정된 숫자이기 때문에, 고정된 만큼 영향을 주기 때문에, 증가율에 시점에서는 무시하겠다는 것이다.

 

 마찬가지로,

O(2n²) => O(n²)

n² 또한 차원이 늘어나지 않는 한, 앞에 있는 상수는 무시한다.

 

 

🌈 참고

www.youtube.com/watch?v=6Iq5iMCVsXA

[자료구조 알고리즘] 빅오(Big-O)표기법 완전정복

 

cjh5414.github.io/big-o-notation/

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

m.blog.naver.com/kks227/220769859177

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

www.youtube.com/watch?v=dxStJ6lCqPQ