⭐ Big-O 표기법이란?

Big-o 표기법은 알고리즘의 성능을 수학적으로 표기한 것이다.
알고리즘의 성능을 측정하는 지표에는 시간복잡도와 공간복잡도가 있다.

• 시간 복잡도: 특정 크기의 입력을 기준으로 할 때 필요한 연산의 횟수
• 공간 복잡도: 프로그램 실행과 완료에 필요한 공간(메모리)

✒️ 상수는 과감하게 버린다.

• 만약 O(2N)과 같이 데이터가 두 배가 될 때의 시간 복잡도를 구하고 싶을 때에도 O(n)으로 표기한다. 실질적인 시간이 아니라 데이터가 늘어남에 따른 시간 복잡도를 계산하고 싶기 때문이다.
  
  

⭐ 시간 복잡도

1) O(n)

• 상수시간: 데이터 크기에 비례해서 처리 시간이 늘어난다.

2) O(n²)

• n을 두 번 루프를 돈다. (이중 for문을 n만큼 돈다.)

3) O(nm)

• n을 m만큼 루프를 돈다.

4) O(n³)

• n을 세 번 루프를 돈다.

5) O(2ⁿ)

• 피보나치 수열에 관한 시간 복잡도다.

6) O(log n)

• 이진 검색 트리에서 주로 사용되는 시간 복잡도다.

7) O(sqrt(n))

• 루트를 사용할 때 사용되는 시간 복잡도이다. 예를 들어 n=9일 때, sqrt(n) 값은 루트를 적용한 3이다.

⭐ 알고리즘별 시간 복잡도