복잡도

시간 복잡도

• 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계
• 알고리즘 로직이 ‘얼마나 오랜 시간’ 걸리는지
• 입력된 N 의 크기에 따라 실행되는 조작의 수 ( 연산수치, 명령어의 실행 횟수 )
• 빅오 표기법 사용, Ex. 10n^2 + n 은 O(n^2)

O(1) – 상수 시간 : 문제를 해결하는데 오직 한 단계만 처리함. O(log n) – 로그 시간 : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬. O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐. O(n log n) : 문제를 해결하기 위한 단계의 수가 N*(log2N) 번만큼의 수행시간을 가진다. (선형로그형) O(n^2) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱. O(C^n) – 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱.

 

시간 복잡도 유형

• 하나의 루프를 사용하여 단일 요소 집합을 반복 하는 경우 : O (n)
• 컬렉션의 절반 이상 을 반복 하는 경우 : O (n / 2) -> O (n)
• 두 개의 다른 루프를 사용하여 두 개의 개별 콜렉션을 반복 할 경우 : O (n + m) -> O (n)
• 두 개의 중첩 루프를 사용하여 단일 컬렉션을 반복하는 경우 : O (n²)
• 두 개의 중첩 루프를 사용하여 두 개의 다른 콜렉션을 반복 할 경우 : O (n * m) -> O (n²)
• 컬렉션 정렬을 사용하는 경우 : O(n*log(n))

 

공간 복잡도

• 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양
• 정적 변수와 동적 변수의 공간 모두 포함

 

빅오 표기법

• 최상 (Big-Ω Notation) / 평균 (Big-θ Notation) / 최악 (Big-O Notation) 의 세 표기법 중 최악인 빅오표기법으로 경우를 판단하여 평균과 가까운 성능을 예측
• Big-O로 측정되는 복잡성에는 시간과 공간 복잡성이 포함