알고리즘) 시간 복잡도 / 빅오 표기법이 도대체 뭘까

 

 

 

안녕하세요 :) 소들입니다!

요즘 자료구조와 알고리즘을 공부하고 있는 기념 😇

오늘은 어찌보면 꼭 알아두어야 할 개념인 

시간 복잡도와 빅오 표기법에 대해 공부해보려고 해염!!!

 

휴..!!! 어렵지 않게 설명하려고 노력해보겠슴돠

모든 포스팅은 편의 말투로 합니다~!!

 

 

 

 

1. 시간 복잡도 / 공간 복잡도

 

먼저, 알고리즘을 한번이라도 시도한 사람이라면

시간 복잡도와 공간 복잡도에 대해 들어봤을 것임!!

이것들이 뭔지 먼저 짚고 가자 :)

 

 

 

1-1. 시간 복잡도

 

알고리즘의 실행 속도

 

자, 시간 복잡도라는 개념은 바로 알고리즘의 실행 속도를 말하는 것임!!

알고리즘이란 것은 답이 없기 때문에

하나의 문제를 풀 때 여러가지 코드를 이용하여 풀 수 있음!

근데 방법은 여러 가지라 해도, 가장 실행 속도가 적은 최적의 코드를 짜야하지 않겠음??

 

따라서 알고리즘을 짤 땐 이 시간 복잡도라는 것이 매우매우 중요함!

자, 다음과 같이 서울에서 부산을 가는 방법의 순서가있다고 해보셈

 

 

1. 자동차 문열기

2. 자동차 시동 걸기

3. 서울에서 부산까지 운전하기

4. 자동차 시동 끄기

5. 자동차 문 닫기

 

이런 순서에서 가장 시간이 오래 걸리는 것은 무엇일까??

누가봐도 3번 서울에서 부산까지 운전하기일 것임

 

이게 시간 복잡도랑 무슨 상관이냐면,

우리가 코드를 짜는 것은 모두~ 시간 복잡도를 계산할 수 있음

예를 들어 1부터 10까지 출력하는 다음과 같은 코드가 있음

 

 

var count = 10
for num in 1..<count {
    print(num)
}

 

 

이때

첫 줄에서 count란 변수를 선언하는 것 또한 시간 복잡도로 계산할 수 있음

하지만, 이는 자동차 문열고, 닫고 하는 것 만큼 부수적이고 크게 영향을 끼치지 않음!

 

그럼 이 코드에서 가장 오래걸리는 것은 무엇이냐?

count만큼 print를 반복해서 호출하는 반복문이 핵심임!

 

따라서, 시간 복잡도를 계산할 때 "보통" 가장 핵심이 되는 것은

바로 입력에 따른 반복문이 얼마큼 반복되느냐! 라는 것임 :)

(보통인 만큼 물론 아닌 경우도 있음)

 

그럼 이 시간 복잡도를 나타내는 데 사용되는 성능 표기법이 

다음과 같이 세 가지가 있는데

 

 Big O(빅-오) 표기법 : O(N) 

알고리즘 최악의 실행 시간을 표기

아무리 최악의 상황에도, 이정도 성능은 보장한다는 의미

 

 Ω (오메가) 표기법 : Ω(N) 

알고리즘 최상의 실행 시간을 표기

 

 Θ(세타) 표기법 : Θ(N) 

알고리즘 평균 실행 시간을 표기

 

 

이 중에서 가장 많이 일반적으로 사용하는것이

바로, 빅오 표기법이기 때문에 빅오 표기법만 알아도 문제 없음 :)

그럼 빅오 표기법을 알기 전에, 공간 복잡도에 대해서도 간단히 알고가자!

 

 

 

1-2. 공간 복잡도

 

알고리즘이 사용하는 메모리의 크기

 

공간 복잡도는 알고리즘이 실행될 때

메모리를 얼마나 사용하느냐!를 나타내는 것임!

 

근데, 보통 알고리즘 할 때 시간 복잡도만 보고

공간 복잡도를 잘 보지 않는 이유는, 요즘 메모리에 대한 발전으로

중요도가 낮아졌기 때문에 크게 신경쓰지 않아도 됨!!

따라서, 우린 시간 복잡도만 알고가도 됨 :)

 

 

 

 

2. 빅오 표기법

 

위에서, 빅오 표기법이란 시간 복잡도를 나타내는 표기법이라고 했음!

그럼 어떻게 표기를 할까?

 

O(입력)

 

으로 표기함!

보통 빅오 표기법을 이용해 시간 복잡도를 나타낼 땐 다음과 같이 표기하는데

 

 

 

 

왼쪽인 O(1)으로 갈 수록 실행 횟수가 적은 것, 즉 시간 복잡도가 낮은 것이고!

오른쪽인 O(n!)으로 갈 수록 실행 횟수가 많은 것, 즉 시간 복잡도가 높은 것임!

 

뭔말인지 이해한 사람?ㅎ

실제 O(1)과 O(n), O(n^2)에 대해 예로 보여주겠음!!!

 

 

 

2-1. O(1)

 

만약 다음과 같은 함수가 있음

 

 

func sayHello(n: Int) {
    print("Hello!")
}

 

 

위 코드는 입력 n이 어떻든 말든 Hello라는 메세지를 한 번만 출력함!

따라서 이를 n과 상관 없이 상수 1만큼 실행 되었다고 표현함!

자, 이렇게 입력인 n과 관련이 없는 경우,

 

O(1)

 

이라고 표현함!

자 그럼 다음과 같이 printf라는 함수를 3번 출력했음

 

 

func sayHello(count: Int) {
    print("Hello!")
    print("Hello!")
    print("Hello!")
}

 

 

그럼 이런 경우엔 상수 3만큼 실행된 것이니 O(3)이 될까?

놉! 상수가 몇 번 실행되었는지는 취급하지 않음!

다만 입력 n과 상관 없이 실행될 경우 이는 마찬가지로 O(1)로 표기함

 

 

 

2-2. O(n)

 

자 이번엔 다음과 같은 함수가 있음

 

 

func sayHello(n: Int) {
    for _ in 0..<n {
        print("Hello!")
    }
}

 

 

이번엔 입력 n만큼 print 출력을 반복하고 있음

자, 위에서도 말했듯이 시간 복잡도에서 보통 중요한 것은 뭐다? 반복문이다!

 

위 함수는 입력 n만큼 반복문을 실행하니,

따라서 위 함수의 시간 복잡도를 빅오 표기법으로 표기하면

 

O(n)

 

이 되는 것임!!

자 그럼 만약 다음과 같이 위 O(n)을 가지는 코드를 10번 반복하게 했음

 

 

func sayHello(count: Int) {
    for _ in 0..<10 {
        for _ in 0..<count {
            print("Hello!")
        }
    }
}

 

 

이 경우엔 실제 실행 횟수는 10n이 될 것임!

그럼 빅오 표기법으로도 O(10n)이 될까??? (count가 3이면 30번 반복할테니까!)

 

당연히 아님 !!

빅오표기법은 n만 중요함 n앞에 어떤 상수가 붙던, n뒤에 어떤 상수가 붙던 다 필요 없고

 이미 정의된 표기법으로만 표기함! 

따라서 위의 코드 또한 빅오 표기법으론 O(n)이 되는 것임

 

 

 

2-3. O(n^2)

 

자 마지막으로 다음과 같은 함수가 있음

 

 

func sayHello(n: Int) {
    for _ in 0..<n {
        for _ in 0..<n {
            print("Hello!")
        }
    }
}

 

 

이 경우엔 반복문 두 개가 중첩되어 실행 되었는데,

이 반복문 두 개가 모두 입력 n에 의해 실행 되었음!

만약 n이 10이면 총 100번이 실행될 것임! 그럼 이땐

 

O(n^2)

 

으로 표기함!!

이또한 만약 코드를 더 추가하고 변수도 선언하고 해서 300n^2 + 10 만큼 실행되었다 하더라도,

앞서 누누히 말했듯 빅오 표기법으론 O(n^2)으로만 표기함!!!

 

 

 

이런 식으로 표현하는 것이 빅오 표기법 :)

그 외의 빅오 표기법 예제는 다음 표를 참고하셈

 

 

Complexity	1	10	100
O(1)	1	1	1
O(log N)	0	2	5
O(N)	1	10	100
O(N log N)	0	20	461
O(N^2)	1	100	10000
O(2^N)	1	1024	1267650600228229401496703205376
O(N!)	1	3628800	표현 불가

 

 

 

 

3. 시간 복잡도 예제

 

시간 복잡도를 이해하기 쉬운 예제 하나를 들어보겠셈

입력 값 n을 받아서 1~n 까지 더해서 출력하는 함수를 두 가지 방법으로 만들어 보겠셈

 

 

 

3-1. 반복문을 이용한 풀이

 

 

func sum(n: Int) {
    var total = 0
    for num in 0..<n {
        total += num
    }
    print(total)
}

 

 

이렇게 반복문을 이용해서 풀이한 경우,

입력 n만큼 반복문이 실행되어 시간 복잡도의 경우

 

O(n)

 

이 됨

 

 

 

3-2. 수식을 이용한 풀이

 

 

func sum(n: Int) {
    var total = n * (n + 1) / 2
    print(total)
}

 

 

자, 이렇게 1~n까지 합을 구하는 수식을 이용해서 풀 경우,

입력 n과 상관 없이 상수로 실행되기 때문에 시간 복잡도의 경우

 

O(1)

 

이 됨

 

 

 

따라서, O(n)보단 O(1)이 시간 복잡도가 낮아,

반복문을 n만큼 돌리는 1번 방식보다, 수식을 이용한 2번 방식이 시간 복잡도 상 더 효율적인 코드임!

 

 

 

 

 

 

 

 

.

.

.

log에 대해서도 다뤄보고 싶은데

보통 정렬 알고리즘에서 나오는 표기법이라네영 :)

정렬 알고리즘도 곧 포스팅할 예정이라 그때 다뤄 볼게요!!!

 

잘못된 내용이나 피드백은 댓글 주세요!! 👀

이 포스팅은 강의 + 출처 포스팅을 통해 공부한 내용을 토대로

(내가) 알기 쉽게 재작성하였씁니다

 

출처 : 

 

blog.chulgil.me/algorithm/