💁‍♀️ 알고리즘?

• 문제를 해결하기 위한 일련의 절차

  ---

💁‍♀️ 계산복잡도?

• 알고리즘이 문제를 해결하는 데 필요한 계산 자원(시간, 메모리 등)의 양을 나타내는 개념입니다.

• 계산 복잡도를 측정하는 데에는 주로 시간 복잡도(Time complexity)와 공간 복잡도(Space complexity)가 사용됩니다.

• 시간 복잡도는 알고리즘이 문제를 해결하는 데 걸리는 시간의 양을 나타냅니다. 입력 크기에 따라 시간이 어떻게 증가하는지를 나타내는데, 이를 Big-O 표기법으로 나타내는 경우가 많습니다.

  • 예를 들어 O(n)는 입력 크기 n에 비례하여 시간이 증가하는 알고리즘을 나타내며, O(1)은 입력 크기와 상관없이 일정한 시간에 문제를 해결하는 알고리즘을 나타냅니다.

• O(1)

  입력값(N)이 증가해도 실행시간은 동일한 알고리즘, index로 접근하여 바로 처리할 수 있는 연산 과정의 시간 복잡도 → 기본 연산 수라고 생각하면 편함

  ex) stack의 push, pop

• O(log N)

  연산이 한 번 실행될 때 마다 데이터의 크기가 절반 감소하는 알고리즘 (log의 지수는 항상 2)

  ex) binary search 알고리즘, tree 형태 자료구조 탐색

• O(N)

  입력값(N)이 증가함에 따라 실행시간도 선형적으로 증가하는 알고리즘

  ex) 1중 for문

• O(N log N)

  O(N)의 알고리즘과 O(log N)의 알고리즘이 중첩된 형태

  ex) 퀵 / 병합 / 힙 정렬

• O(N^2)

  O(N)의 알고리즘과 O(log N)의 알고리즘이 중첩된 형태

  ex) 2중 For 문, 삽입/거품/선택 정렬

• O(2^N)

  빅오 표기법 중 가장 느린 시간 복잡도로 주로 재귀적으로 수행하는 알고리즘이 이에 해당

  ex) fibonacci 수열

💁‍♀️ 시간 복잡도 표기법

• Big-O(빅 오) 표기법: 알고리즘 최악의 실행 시간을 표기한다. 가장 많이 사용하는 표기법이다. 최소한 보장되는 성능을 표기하기 때문에 가장 일반적으로 사용한다.

• Big-Ω(빅 오메가) 표기법: 알고리즘 최상의 실행 시간을 표기한다.

• Big-θ(빅 세타) 표기법: 알고리즘 평균 실행 시간을 표기한다.