알고리즘 → 문제를 해결하는 과정

시간 복잡도

• 알고리즘이 걸릴 수 있는 최소 시간 = Lower bound
• 걸릴 수 있는 최대 시간 = Upper bound

https://vercel-prac-gamma.vercel.app/

시간복잡도

로직이 실행되는데 입력 값에 얼마나 많은 시간이 걸리는가?

→ Big-O 표기법을 사용 (점진적으로 데이터가 커짐에 따라 어떻게 표기)

1) O(1) : 상수 시간

• 입력 크기와 관계없이 딱 한 번 계산.

  예: 배열에서 인덱스로 값 찾기

2) O(log n) : 로그 시간

• 입력이 커질수록 조금만 늘어남.

  • binarySearch

  예: 이진 탐색 (n=1000일 때 10번만 확인하면 끝)

3) O(n) : 선형 시간

• 입력 크기만큼 비례해서 실행.

  • reverse

  예: 배열 전체 탐색

4) O(n log n)

• n보다 살짝 빠르게 커지는 정도.

  → 적어도 nlogn까지가 효율적이다.

  예: 효율적인 정렬 알고리즘(퀵정렬, 병합정렬)