복잡도(Complexity)
- 시스템이나 시스템 구성 요소 또는 소프트웨어의 복잡한 정도를 나타내는 말
- 시스템 또는 소프트웨어를 어느 정도의 수준까지 테스트해야 하는지, 개발하는데 어느 정도의 자원이 소요되는지 예측하는데 사용됨
- 복잡도가 높으면 장애가 발생할 수 있음
-> 정밀한 테스트로 미리 오류 제거해야됨 - 복잡도 측정 방법
: LOC(Line Of Code)
: 순환 복잡도(Cyclomatic Complexity)
시간 복잡도
알고리즘의 실행시간, 수행하는 연산 횟수를 수치화한 것
빅오 표기법
알고리즘의 실행시간이 최악일 때를 표기하는 방법
-
신뢰성이 떨어지는
오메가 표기법이나 평가하기 까다로운세타 표기법에 비해 성능을 예측하기 용이하여 주로 사용됨 -
O(1)
: 입력값에 관계 없이 일정하게 하나의 단계만 거침
: 스택의 삽입/삭제 -
O(log₂n)
: 단계가 입력값(n) 또는 조건에 의해 감소
: 이진 트리, 이진 검색 -
O(n)
: 단계가 입력값(n)과 1:1의 관계
: for문 -
O(nlog₂n)
: 단계가 n(log₂n)번만큼 수행됨
: 힙 정렬, 2-Way 합병 정렬 -
O(n²)
: 단계가 입력값(n)의 제곱만큼 수행
: 삽입 정렬, 쉘 정렬, 선택 정렬, 버블 정렬, 퀵 정렬 -
O(2^n)
: 단계가 2의 입력값(n) 제곱만큼 수행
: 피보나치 수열
순환 복잡도
Cyclomatic Complexity
- 논리적인 복잡도를 측정하기 위한 소프트웨어의 척도
- 맥케이브 순환도 또는 맥케이브 복잡도 메트릭이라고도 함
- 제어 흐름도 이론에 기초를 둠
계산 방법
제어 흐름도 G에서 순환 복잡도 V(G)
방법 1. 순환 복잡도는 제어 흐름도의 영역 수와 일치함
방법 2. V(G) = E(화살표 수) - N(노드 수) + 2
11 - 9 + 2 = 4
노력형 인간