063 복잡도 - 4장 애플리케이션 테스트 관리 - 2과목 소프트웨어 개발

1. 복잡도 개요

- 시스템이나 시스템 구성 요소 또는 소프트웨어의 복잡한 정도를 나타낸다

- 시스템 / 소프트웨어를 어느 정도의 수준까지 테스트해야 하는지 또는 개발하는데 어느 정도의 자원이 소요되는 예측하는데 사용

- 복잡도가 높으면 장애 발생 확률이 높아짐

- 측정 방법 : LOC(Line Of Code), 순환 복잡도(Cyclomatic Complexity) 등

     -> 소프트웨어의 개별적인 기능에 대해 원시 코드 라인 수의 비관치, 낙관치, 기대치를 측정하여 예측치를 구하고 이를 이용해 비용 산정

 

2. 시간 복잡도

- 알고리즘의 실행 시간

- 실행시간은 하드웨어 성능이나 언어에 따라 달라지기 때문에 시간이 아닌 명령어 실행 횟수를 표기한다. 이를 점근 표기법이라 한다

- 점근 표기법의 종류

빅오 표기법	- 실행시간이 최악일 때를 표기하는 방법 - 입력값에 대해 알고리즘을 수행했을 때 명령어 실행 횟수는 어떠한 경우에도 표기 수치보다 많을 수 없다
세타 표기법	- 실행시간이 평균일 때를 표기
오메가 표기법	- 실행시간이 최상일 때를 표기 - 입력값에 대해 알고리즘을 수행했을 때 명령어 실행 횟수는 어떠한 경우에도 표기 수치보다 적을 수 없다

 

3. 빅오 표기법

- 실행시간이 최악일 때를 표기

- 성능 예측에 가장 용이

O(1)	입력값(n)에 관계 없이 일정하게 문제 해경에 하나의 단계만을 거친다 예) 스택의 삽입, 삭제
O(log2n)	문제 해결에 필요한 단계가 입력값(n) 또는 조건에 의해 감소한다 예) 이진 트리, 이진 검색
O(n)	문제 해결에 필요한 단계가 입력값(n)과 1:1 관계를 가진다 예) for문
O(nlog2n)	문제 해결에 필요한 단계가 n(log2n)번만큼 수행된다 예) 힙 정렬, 머지 정렬
O(n^2)	문제 해결에 필요한 단계가 입력값(n)의 제곱만큼 수행된다 예) 삽입 정렬, 쉘 정렬, 선택 정렬, 버블 정렬, 퀵 정렬
O(2n)	문제 해결에 필요한 단계가 2의 입력값(n) 제곱만큼 수행된다 예) 피보나치 수열

 

4. 순환 복잡도

- 한 프로그램의 논리적인 복잡도를 측정하기 위하 소프트웨어의 척도

- 맥케이브 순환도(McCabe's Cyclomatic) 또는 맥케이브 복잡도 메트릭(McCabe's Complexity Metrics)이라고도 한다

- 제어 흐름도 이론에 기초를 둔다

- 순환 복잡도로 계산된 값은 프로그램의 독립적인 경로의 수를 정의한다

- 모든 경로가 한 번 이상 수행되었음을 보장하기 위해 행해지는 테스트 횟수의 상한선을 제공한다

- 제어 흐름도 G에서 순환 복잡도 V(G)는 다음과 같이 계산한다

     방법 1 - 순환 복잡도는 제어 흐름도의 영역 수와 일치하므로 영역 수를 계산한다

     방법 2 - V(G) = E - N + 2 

                  E는 화살표 수, N은 노드의 수