빅 오 표기법

빅 오

입력값이 커질 떄 알고리즘의 실행 시간(시간 복잡도)과 함께 공간 요구사항(공간 복잡도)이

어떻게 증가하는지를 분류하는데 사용한다. → 알고리즘의 효율성을 분석하는데 활용

빅오

---

입력값이 무한대로 향할 대 함수의 상한을 설명하는 수학적 표기 방법

점근적 실행 시간(Asymptotic Running Time)을 표기할 때 가장 널리 쓰이는 수학적 표기법 중 하나

컴퓨터의 빠른 처리 능력을 감안하더라도

입력의 크기가 충분히 큰 경우에는 알고리즘의 효율성에 따라 수행시간이 크게 차이가 난다.

점근적 실행 시간

= 시간 복잡도 (Time Complexity)

= 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도(Computational Complexity)

계산 복잡도를 표기하는 대표적인 방법 → 빅 오

• 빅오로 시간 복잡도를 표현할 때는 최고차항만을 표기, 계수는 무시

💡 ( n→∞ 일때, n의 계수나 다른 낮은 차항들은 무시 가능하기 때문)

ex) 입력값 n에 대해 4n²+3n+4번 만큼 계산하는 함수 ⇒ 최고차항인 4n²에서 n²만 고려

⇒ 시간 복잡도 O(n²)

예시

---

O(1)

입력값이 아무리 커도 실행시간 일정. 최고의 알고리즘!

상수 시간을 갖는 알고리즘을 홍보한다면 일단 의심…

이것이 실행된다 해도 상수값이 매우 크다면 사실상 일정한 시간의 의미가 없다.

O(log n)

실행 시간이 입력값에 영향을 받음.

하지만 로그는 매우 큰 입력값에도 크게 영향을 받지 않는 편

웬만한 n의 크기에 대해서도 매우 견고함

O(n)

입력값만큼 실행 시간이 영향을 받음. ⇒ 선형 시간 알고리즘이라고 한다

정렬되지 않은 리스트에서 최댓값 또는 최솟값을 찾는 경우가 이에 해당

이 값을 찾으려면 모든 입력값을 적어도 한번 이상은 살펴봐야 한다

O(n log n)

병합 정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘에 해당

적어도 모든 수에 대해 한번 이상은 비교해야하는 비교 기반 정렬 알고리즘은

아무리 좋은 알고리즘도 이것보다 빠를 수 없다

물론 입력값이 최선이 되면 비교를 건너뛰어 O(n)이 될 수 있다. → Timsort logic

O(n²)

버블 정렬 같은 비효율적인 알고리즘

O(2ⁿ)

피보나치 수를 재귀로 계산하는 알고리즘

n²과 혼동하는 경우가 있는데 2ⁿ이 훨씬 더 크다.

O(n!)

각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제(TSP)를

brute force 풀이로 풀이할 경우

입력값이 조금만 커져도 웬만한 시간 내에는 계산이 어렵다.

공간 복잡도를 표현하는 빅 오

---

‘시간과 공간이 Trade-off’

실행시간이 빠른 알고리즘은 공간을 많이 사용하고,

공간을 적게 차지하는 알고리즘은 실행 시간이 느린 경우가 많다.

상한과 최악

---

빅오(O)는 상한(Upper Bound)를 의미

💡 상한은 최악이 아니다!

빅오 표기법은 정확하게 쓰기에는 너무 길고 복잡한 함수를 ‘적당히 정확하게’ 표현하는 방법

최악의 경우/평균적인 경우의 시간 복잡도가 아니다!

빅오 표기법은 주어진(최선/최악/평균) 경우의 수행 시간의 상한을 나타낸다!

즉, 최악 보다 더 나쁜 수행시간을 빅오(O)라고 말해도 사실이다.

빅오는 수행 시간이 ~ 보다는 확실히 낮을 것이다라고 적당히 정확하게 표현한 것이기 때문이다.

분할 상환 분석

---

[ 좋은 글 ]

어떤 자료 구조의 특정 연산들은 수행 시간이 상황이나 상태에 따라 달라지는 경우가 있다.

최악의 경우 매우 긴 시간을 요구하지만 대부분의 경우 짧은 시간이면 충분하다면

이 연산들을 n번 완료하는데 필요한 시간의 상한을 구할 때

최악의 경우 x n 으로 생각하는 것은 연산들의 실제 능력을 과소평가 하는것이다.

대신에 n번을 처리하는데 필요한 시간의 상한을 적절하게 구해

이 연산들이 평균적으로 상한/n 의 시간에 동작한다고 말할 수 있을 것이다.

이때, 상한/n의 값이 상한보다 한참 작다면 실제로는 더 좋은 성능을 낸다는 것을 알 수 있다.

이렇게 어떤 자료 구조의 연산들의 임의의 sequence가 주어졌을 때,

sequence 위의 모든 연산들이 수행되는 동안

각 연산의 평균적인 수행 시간을 분석하는 방법을

분할 상환 분석(amortized analysis) 라고 한다.

sequence의 최악의 수행 시간을 잘 분할하여 다시 sequence에 골고루 상환(나눔) 해준다는 의미.

이런 분할 상환 분석과 대조되는 분석방법은

최악의 경우 걸리는 시간을 분석하는 것이므로

최악의 경우 분석(worst-case analysis)라고 한다.

! 주의

분할 상환 분석과 평균 경우 분석은 서로 다른 것!

• 분할 상환 분석

: 확률의 개념이 포함되지 x , 임의의 연산 sequence가 주어졌을 때

이를 수행하는 동안 각 연산의 평균 수행 시간

• 평균 경우 분석(average-case analysis)

: 입력을 결정하는 특정 확률 분포(probability distribution)가 필요.

해당 분포에 따라서 입력이 주어질 때, 알고리즘이 모두 수행되는데 필요한 시간의 평균값

병렬화

---

일부 알고리즘은 병렬화로 실행 속도를 높일 수 있다.

그래서 최근에는 알고리즘이 병렬화가 가능한지도 알고리즘의 우수성을 평가하는 중요한 척도 중 하나가 되었다.