[정보처리기사 필기] 애플리케이션 테스트 관리 - 052. 복잡도

1. 복잡도의 개요

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

• 시스템 또는 소프트웨어를 어느 정도의 수준까지 테스트해야 하는지 또는 개발하는데 어느 정도의 자원이 소요되는지 예측하는데 사용
• 시스템의 복잡도가 높으면 장애가 발생할 수 있으므로 정밀한 테스트를 통해 미리 오류를 제거할 필요가 있음
• 주요 복잡도 측정 방법 : LOC, 순환 복잡도 등

2. 시간 복잡도

알고리즘의 실행시간, 알고리즘을 수행하기 위해 프로세스가 수행하는 연산 횟수를 수치화한 것

• 시간 복잡도와 알고리즘의 관계 : 비례
  • 시간 복잡도가 낮을수록 알고리즘의 실행시간이 짧음
  • 시간 복잡도가 높을수록 알고리즘의 실행시간이 길어짐
• 알고리즘의 실행시간이 하드웨어적 성능이나 프로그래밍 언어의 종류에 따라 달라지기 때문에 시간이 아닌 명령어의 실행 횟수를 표기 (점근 표기법)
• 점근 표기법의 종류
  • 빅오 표기법 Big-O Notation
    • 알고리즘의 실행시간이 최악일 때를 표기하는 방법
    • 입력값에 대해 알고리즘을 수행했을 때 명령어의 실행 횟수는 어떠한 경우에도 표기 수치보다 많을 수 없음
  • 세타 표기법
    • 알고리즘의 실행시간이 평균일 때를 표기하는 방법
    • 입력값에 대해 알고리즘을 수행했을 때 명령어 실행 횟수의 평균적인 수치를 표기
    • 평가하기 까다로움
  • 오메가 표기법
    • 알고리즘의 실행시간이 최상일 때를 표기하는 방법
    • 입력값에 대해 알고리즘을 수행했을 때 명령어의 실행 횟수는 어떠한 경우에도 표기 수치보다 적을 수 없음
    • 신뢰성이 떨어짐

3. 빅오 표기법 Big - O Notation

• O(1) : 입력값(n)에 관계없이 일정하게 문제 해결에 하나의 단계만을 거침
• O(log₂n) : 문제 해결에 필요한 단계가 입력값(n) 또는 조건에 의해 감소
• O(n) : 문제 해결에 필요한 단계가 입력값(n)과 1:1 관계를 가짐
• O(nlog₂n) : 문제 해결에 필요한 단계가 n(log₂n)번만큼 수행
• O(n²) : 문제 해결에 필요한 단계가 입력값(n)의 제곱만큼 수행
• O(2ⁿ) : 문제 해결에 필요한 단계가 2의 입력값(n) 제곱만큼 수행

4. 순환 복잡도

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

• 맥케이브 순환도, 맥케이브 복잡도 메트릭
• 제어 흐름도 이론에 기초
• 순환 복잡도를 이용하여 계산된 값은 프로그램의 독립적인 경로의 수를 정의, 모든 경로가 한 번 이상 수행되었음을 보장하기 위해 행해지는 테스트 횟수의 상한선 제공
• 제어 흐름도 G에서 순환 복잡도 V(G) 계산 방법
  • 순환 복잡도는 제어 흐름도의 영역 수와 일치하므로 영역 수를 계산
  • V(G) = E - N + 2 
  • 순환 복잡도 = 화살표의 수 - 노드의 수 + 2
  • E는 화살표 수, N은 노드 수