Complexity

Complexity(복잡도) : 알고리즘의 성능을 나타내는 척도

Time Complexity(시간 복잡도)

• 시간적 측면에서 알고리즘의 성능을 평가하는 지표
• 알고리즘을 위해 필요한 연산의 횟수(얼마나 오래 걸리는지)

Space Complexity(공간 복잡도)

• 공간적 측면에서 알고리즘의 성능을 평가하는 지표
• 알고리즘을 위해 필요한 메모리의 양(얼마나 많은 메모리를 차지하는지)

빅오(Big-O)

• 점근적 상한선(Asymptotic upper bound)
• 주어진 알고리즘이 아무리 나빠도 비교하는 함수와 같거나 좋다.
• N0을 기준으로 n0보다 오른쪽에 있는 모든 n에 대해서 함수 f(n)은 함수 c g(n)보다 작거다 같다.
• O(g(n)) = {f(n) : there exist positive constants c and n0 such that 0<= f(n) <=cg(n) for all n>=n0}

빅오메가(big-Ω)

• 점근적 하한선(Asymptotic lower bound)
• 주어진 알고리즘이 아무리 좋아도 비교하는 함수와 같거나 나쁘다.

빅세타(big-Θ)

• 점근적 상한선과 하한선의 교집합(Asymptotic tighter bound)
• 주어진 알고리즘이 아무리 좋아지거나 나빠지더라도 비교하는 함수의 범위 안에 있다.

Big-O notation

• 데이터 입력값 (n)이 충분히 크다고 가정하고 있고, 알고리즘의 효율성 또한 데이터 입력값(n)의 크기에 따라 영향맞기 때문에 상수항, 최고차수 이하의 항들은 모든 무시한다.
  Ex)

1. O(1) : 스택에서 Push, Pop
2. O(log n) : 이진트리
3. O(n) : for 문
4. O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)
5. O(n^2) : 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
6. O(2^n) : 피보나치 수열