230821 - 빅오 표기법 ( Big O natation)

오늘 내가 배운 것

1. 빅오 표기법이란?

2. 표기방법

3. 잘못된 표기방법

4. 복잡도 알고리즘 비교

5. 시간 복잡도와 공간 복잡도의 상호 관계

 

 

1. 빅오 표기법이란?

빅오 표기법(Big O notation)은 알고리즘의 효율성을 설명할 때 주로 사용되는 수학적 표기법이다. 이 표기법은 입력 크기가 커짐에 따라 어떻게 알고리즘이 수행되는지, 얼마나 많은 리소스(시간, 메모리 등)가 필요하는지를 설명하는 데 사용된다.

 

빅오 표기법을 이용해서 시간 복잡도, 공간 복잡도에 따라 표기를 할 수 있다.

시간 복잡도 : 알고리즘이 실행되는데 필요한 단계의 수나 계산 시간을 표현한다.

공간 복잡도 : 알고리즘이 실행되는 동안 필요한 메모리 양을 나타낸다.

 

 

2. 표기 방법

• O(1) : 상수 시간/공간 복잡도 : 입력 크기와 관계없이 일정한 시간/공간이 소요된다.
  • 예) 단순 연산, 배열의 특정 인덱스 접근
• O(log n) : 로그 시간/공간 복잡도 : 로그배만큼 시간/공간이 소요된다.
  • 예) 이진 탐색
• O(n) : 선형 시간/공간 복잡도 : 입력 크기에 비례하여 시간/공간이 소요된다.
  • 예) 단순 탐색, 동적 배열, for문
• O(n log n) : 선형 로그 시간/공간 복잡도 : 입력 크기와 로그배만큼 시간/공간이 소요된다.
  • 예) 병합정렬, 퀵 정렬
• O(n^2) : 제곱 시간/공간 복잡도 : 입력 크기의 제곱에 비례하는 시간/공간이 소요된다.
  • 예) 버블 정렬, 이중 for문
• O(2^n) : 지수 시간/공간 복잡도 : 입력 크기에 대해 지수적으로 시간/공간이 소요된다.
  • 예) 피보나치수열, 재귀

 

3. 잘못된 표기방법

상수항, 영향력이 없는 항들은 무시한다.

• O(2n) → O(n)
• O(500) → O(1)
• O(13n^2) → O(n2)
• O(2n+100) → O(n)
• O(100n+10) → O(n)
• O(n^2+100n) → O(n^2)
• O(100n^2+100) → O(n^2)

 

4. 복잡도 알고리즘 비교

O(1) > O(log n) > O(n) > O(n log n) > O(n^2) > O(2^n)

상수 > 로그 > 선형 > 선형 로그 > 제곱 > 지수 순으로 효율적이라고 할 수 있다.

상수가 가장 빠르고 효율적이며, 지수 복잡도로 갈수록 입력크기가 커지면 느려지기 때문에 피하는 것이 좋다.

 

 

 

5. 시간 복잡도와 공간 복잡도의 상호 관계

시간 복잡도와 공간 복잡도는 서로 상호 관계가 있을 수 있다.

예를 들어, 메모리(공간)를 더 사용하게 되면 연산을 줄일 수 있고, 반대로 시간을 더 사용하면 메모리를 절약할 수 있다. 대표적으로 캐싱이 있다.

캐싱 : 연산 결과를 저장하여 나중에 같은 계산을 할 때 값을 빠르게 얻을 수 있지만 값을 저장할 메모리가 필요하다.

 

출처 : https://www.udemy.com/course/best-javascript-data-structures/