Big O

빅 오 표기법 (Big-O notation) 이란?

• 알고리즘의 효율성을 표기해주는 표기법
   → 알고리즘의 효율성은 데이터 개수(n)가 주어졌을 때 덧셈, 뺄셈, 곱셈 같은 기본 연산의 횟수

• 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용
   → 시간 복잡도: 알고리즘의 시간 효율성
   → 공간 복잡도: 알고리즘의 공간(메모리) 효율성

• 공간 복잡도를 나타내는 방법
   ◻︎ 빅오(Big-O)
   ◻︎ 빅오메가(Big-Ω)
   ◻︎ 빅세타(Big-Θ)

빅 오 표기법 예제

1. O($1$): 입력 크기에 상관없이 일정한 시간 내에 실행되는 알고리즘이다.
   예를 들어, 배열에서 특정 인덱스의 값을 찾는 경우 O($1$)의 시간 복잡도를 가진다.

2. O($n$): 입력 크기에 비례하여 실행 시간이 선형적으로 증가하는 알고리즘입니다.
   예를 들어, 배열에서 특정 값을 찾는 경우 선형 검색 알고리즘이 O($n$)의 시간 복잡도를 가집니다.

3. O($n^2$): 입력 크기의 제곱에 비례하여 실행 시간이 증가하는 알고리즘이다.
   예를 들어, 이중 루프를 사용하여 2차원 배열에서 모든 요소를 검색하는 경우 O($n^2$)의 시간 복잡도를 가진다.

4. O($log n$): 입력 크기가 증가할수록 실행 시간이 로그 함수의 값에 비례하여 증가하는 알고리즘이다.
   이진 검색 알고리즘이 O($log n$)의 시간 복잡도를 가진다.

5. O($n log n$): 입력 크기에 비례하여 실행 시간이 로그 함수와 선형 함수의 곱에 비례하여 증가하는 알고리즘이다.
   병합 정렬 알고리즘이 O($n log n$)의 시간 복잡도를 가진다.

이 외에도, O($n^3$), O($2^n$), O($n!$) 등 다양한 시간 복잡도가 있다. 이들은 모두 알고리즘의 성능을 분석하는 데에 사용되며, 어떤 알고리즘이 더 효율적인지 판단할 때 비교적으로 안정적인 기준을 제공한다.

Tip

1. 최악의 경우 시간 복잡도 고려하기.
   알고리즘의 시간 복잡도는 보통 최악의 경우를 기준으로 한다.
   이는 알고리즘이 어떤 상황에서도 일정한 시간 내에 실행됨을 보장하기 위한 것입니다.

2. 상수 계수와 낮은 차수의 항을 무시하자.
   빅 오 표기법에서는 상수 계수와 낮은 차수의 항을 무시한다.
   따라서, 시간 복잡도가 O($3n^2 + 4n + 2$)라면 O($n^2$)으로 간략하게 표기할 수 있다.

3. 루프를 사용하는 알고리즘의 경우, 루프의 반복 횟수를 고려하라.
   루프의 반복 횟수가 입력 크기와 비례하는 경우, 시간 복잡도는 선형적으로 증가한다.

4. 재귀를 사용하는 알고리즘의 경우, 재귀 호출의 깊이를 고려하라.
   재귀 호출의 깊이가 입력 크기와 비례하는 경우, 시간 복잡도는 지수적으로 증가한다.

5. 다양한 알고리즘의 시간 복잡도를 이해하자.
   Big O 표기법은 알고리즘의 성능을 비교하는 데에 유용하다.
   따라서, 다양한 시간 복잡도에 대한 이해가 필요하다.

6. 실험을 통해 알고리즘의 실행 시간을 측정하라.
   Big O 표기법은 알고리즘의 시간 복잡도를 대략적으로 예측하는 데에 사용됩니다.
   그러나, 알고리즘의 실행 시간을 정확하게 예측하기는 어렵습니다.
   따라서, 알고리즘의 실행 시간을 측정하여 실제 성능을 파악하는 것이 중요합니다.

Wikipedia - Big O notation

https://en.wikipedia.org/wiki/Big_O_notation