[알고리즘|기초] Big O 표기법

Big O 표기법

 

Big O 표기법은 알고리즘의 효율성을 설명하는 데 사용되는 수학적 표기입니다.

특히, 알고리즘이 어떤 입력 크기 n에 대해 얼마나 많은 연산을 필요로 하는지를 표현하는데 많이 사용됩니다.

 

시간복잡도

 시간 소요에 대한 척도

 

O(1) - 상수시간

• 입력 데이터의 크기와 상관없이 알고리즘의 실행 시간이 일정합니다. 

O(log n) - 로그시간

•  입력 데이터를 반으로 나눠 가며 문제를 해결 하는 알고리즘 (ex: 이진 탐색)입니다.
•  각 단계에서 입력 데이터의 크기가 절반으로 줄어들기 때문에 로그 시간 복잡도를 가진다.

O(n) - 선형시간

•  입력 데이터의 각 요소를 한번씩만 처리하는 알고리즘에서 나타납니다. 
•  예를 들어 배열의 모든 요소를 순회 하는 경우에 해당하빈다.

O(n log n) - 선형 로그 시간

•  대표 적으로 정렬 알고리즘 (ex: 퀵정렬, 병합정렬) 에서 볼 수 있습니다. 
• 여기서 n은 데이터를 처리하는 것, log n은 데이터를 나누는 것을 의미합니다.

O(n^2)

•  2개의 중첩 루프를 사용 하여 데이터 모든 쌍을 비교 하는 알고리즘 (ex: 버블 정렬 삽입 정렬) 에서 나타납니다.

 

공간복잡도

[...]

Big O 표기법의 단순화

 

1. 상수는 무시합니다.

•  O(5n+2)는 O(n)과 같습니다. 

2. 낮은 차수의 항목은 무시합니다.

•  O(n^2+n)은 O(n^2) 으로 단순화 합니다.

3. 로그의 베이스(밑)는 무시합니다.

•  로그의 베이스가 무엇이든 O(log n)으로 간주됩니다.
•  로그의 성장률은 베이스에 크게 의존하지 않기 때문입니다.

4. [...]

 n * log(n) [...]

 

O(n+n) vs O(n*n)

• Case1. O(n+n)
  • O(n)
• Case2. O(n*n) -
  • O(n^2)