시간 복잡도 (+빅오 표기법) / 공간 복잡도

알고리즘을 공부했다면 한 번쯤 들어본 개념이 바로 시간/공간 복잡도, 그리고 빅오 표기법.. 이런 거 들어보셨을 겁니다. 이 개념이 도대체 무엇인지? 그리고 이걸 고려해서 어떻게 알고리즘 문제를 풀어야 할지 생각해봅시다!!

 

시간 복잡도

시간 복잡도 개념은 알고리즘의 실행 속도를 의미합니다. 

알고리즘 문제의 경우, 결국 하나의 결괏값을 도출하는 코드를 작성하는 작업입니다. 하나의 문제에 대해서 (예를 들어 1에서 10까지 계산하는 것에 있어서 1부터 10까지 반복문을 통해서 계산할 수 있고 / 수식을 사용해서 계산할 수 있습니다. 이외에도 다양한 방법이 있겠죠?) 여러 가지 코드를 이용해서 풀 수 있습니다.

 

이때, 방법은 여러 가지라고 해도 가장 실행 속도가 적은 최적의 코드가 있습니다. 그리고 결국 이것이 정답이 되는 것이죠.

따라서 알고리즘에서 시간 복잡도는 아주 중요합니다.

 

우리가 작성하는 코드는 모두 시간이 걸립니다. 즉, 모든 코드 한 줄 한 줄이 시간 복잡도에 영향을 줍니다. 예를 들어서 1부터 10까지 출력하는 코드를 작성해봅시다.

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

위의 코드에서 var count = 10 이 부분 또한 시간 복잡도에 영향을 줍니다. 그러나 이 코드에서는 그렇게 많은 영향을 끼치지 않습니다. 이 말은 곧, 알고리즘을 짤 때 고려할 부분이 아니라는 것입니다.

>> 위의 코드에서 가장 오래 걸리는 것은 count의 크기만큼 호출되는 print() 문입니다.

>> 따라서, 위의 코드에서 시간 복잡도를 계산할 때 가장 핵심이 되는 것은 바로 입력에 따른 반복문이 얼마큼 반복되느냐!입니다.

(그리고 시간 복잡도에 따라서 해당 알고리즘이 잘 짠 알고리즘인지 그렇지 않은지 판단할 수 있습니다.)

---

 

📌 이 시간 복잡도를 나타내는 데 사용되는 성능 표기법은 크게 세 가지가 있습니다. 📌

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

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

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

 

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

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

 

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

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

 

빅오 표기법

빅오 표기법이란, 시간 복잡도를 나타내는 표기법입니다.

 

앞서 작성한 것과 같이, O(입력)으로 표기합니다. 

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

보통 빅오 표기법을 사용해서 시간 복잡도를 위와 같이 표기하는데,

• 왼쪽으로 갈수록 : 실행 횟수가 적은 것 = 시간 복잡도가 낮은 것
• 오른쪽으로 갈 수록 : 실행 횟수가 많은 것 = 시간 복잡도가 높은 것 

을 의미합니다.

 

빅오 표기법을 표로 나타내면 다음과 같이 나타낼 수 있습니다.

빅오 표기법에서 주의할 것은 🔥 n만 중요하다는 것입니다.🔥 n 앞뒤로 어떤 상수가 붙던지 다 필요 없고 이미 정의된 표기법으로만 표기하는 것입니다.

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	표현 불가

 

시간 복잡도 예제

맨 처음에 예시로 들었던 것을 시간 복잡도로 생각해서 풀어보겠습니다.

문제 : 입력 값 n을 받아서 1~n까지 더해서 출력하는 함수

 

1. 반복문을 이용한 풀이

var input = readLine()

if let input = input {
    if let input = Int(input) {
        sum(n: input)
    }
}

// 실질적인 코드
func sum(n: Int) {
    var total = 0
    for num in 0..<n {
        total += num
    }
    print(total)
}

>> 이렇게 반복문을 이용해서 풀이한 경우, 입력 n만큼 반복문이 실행되어 O(n)의 시간 복잡도가 됩니다.

 

2. 수식을 이용한 풀이

var input = readLine()

if let input = input {
    if let input = Int(input) {
        sum(n: input)
    }
}

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

>> 이와 같이 수식을 이용해서 문제를 풀면, 입력 n과 상관없이 상수로 실행되므로 시간 복잡도가 O(1)이 되는 것을 확인할 수 있습니다.

 

*입력 n과 상관없이 

이 부분이 조금 헷갈릴 수도 있어서 조금 더 설명을 해보겠습니다.

예를 들어, "소깡이 아자자"라는 문장을 출력하는 프로그램이 있다고 생각해봅시다.

func saySokyte(n: Int) {
    print("소깡이 아자자")
}

>> 이 코드는 입력 값 n에 상관없이 "소깡이 아자자" 문장을 한 번만 출력합니다. 이렇게 입력인 n과 상관없는 경우 상수의 크기만큼 실행되는 경우를 O(1)이라고 표현합니다.

func saySokyte(count: Int) {
    for _ in 0..<n {
        print("소깡이 아자자")
    }
}

>> 이 코드에 대해서는 입력 n만큼 반복문이 실행되므로 시간 복잡도가 O(n)이 되는 것을 확인할 수 있습니다.

 

다시 돌아와서.. 수식을 사용할 경우, n의 입력값과 상관없이 해당 코드가 상수의 크기로 실행되기 때문에 시간 복잡도가 O(1)이 되는 것입니다. 

 

✅ 따라서, 반복문을 사용한 풀이 O(n) 보다 수식을 사용한 풀이 O(1)이 시간 복잡도가 낮아, 더 효율적인, 더 최적의 코드라고 할 수 있습니다.

---

공간 복잡도

알고리즘이 사용하는 메모리의 크기를 의미합니다. 공간 복잡도는 알고리즘이 실행될 때 메모리를 얼마나 사용하느냐를 나타냅니다. 

(시간 복잡도만큼의 중요성은 아닙니다. 공간 복잡도는 메모리와 관련된 부분이기 때문에 최근 메모리의 발전으로 그렇게 크게 신경 쓰지 않아도 되기 때문입니다.)