[2과목 소프트웨어 개발] 애플리케이션 테스트 관리 - 064. 복잡도 (Complexity)

• 시스템, 시스템 구성요소, 소프트웨어의 복잡한 정도를 나타내는 말
• 시스템, 소프트웨어를 어느 정도의 수준까지 테스트해야 하는지, 개발하는데 어느 정도의 자원이 소요되는지 예측하는데 사용됨
• 복잡도가 높으면 장애가 발생할 수 있으므로 정밀한 테스트를 통해 미리 오류를 제거
• LOC(Line Of Code), 순환 복잡도(Cyclomatic Complexity)

1. 시간 복잡도

• 알고리즘을 수행하기 위해 프로세스가 수행하는 연산 횟수를 수치화한 것
• 시간 복잡도가 낮을수록 알고리즘 실행시간이 짧고, 높을수록 실행시간이 길어짐
• 빅오 표기법(Big-O Notation)
  • 알고리즘 실행시간이 최악일 때 표기
  • 명령어 실행 횟수는 표기 수치보다 많을 수 없음
• 세타 표기법(Big-θ Notation)
  • 알고리즘 실행시간이 평균일 때 표기
  • 명령어 실행 횟수는 평균적인 수치를 표기
• 오메가 표기법(Big-Ω Notation)
  • 알고리즘 실행시간이 최상일 때 표기
  • 명령어 실행 횟수는 표기 수치보다 적을 수 없음

2. 빅오 표기법(Big-O Notation)

• 알고리즘 실행시간이 최악일 때 표기하는 방법
• 신뢰성이 떨어지는 오메가 표기법이나 평가하기 까다로운 세타 표기법에 비해 성능을 예측하기 용이하여 주로 사용

O(1)	- 입력값(n)에 관계 없이 **일정하게** 문제해결에 하나의 단계만 거침 - 스택 삽입(Push), 삭제(Pop)
O(log2n)	- 문제 해결에 필요한 단계가 입력값(n) 또는 조건에 의해 감소-- 이진트리(Binary Tree), 이진 검색(Binary Search)
O(n)	- 문제 해결에 필요한 단계가 입력값(n)과 1:1의 관계를 가짐 - for문
O(nlog2n)	- 문제 해결에 필요한 단계가 n(lon2n)번 만큼 수행됨 - 힙 정렬(Heap Sort), 2-Way 합병 정렬(Merge Sort)
O(n2)	- 문제 해결에 필요한 단계가 입력값(n)의 제곱만큼 수행됨 - 삽입 정렬(Insrtion Sort), 쉘 정렬(Shell Sort), 선택 정렬(Selection Sort), 버블 정렬(Bubble Sort), 퀵 정렬(Quick Sort)
O(2n)	- 문제 해결에 필요한 단계가 2의 입력값(n) 제곱만큼 수행됨 - 피보나치 수열(Fibonacci Sequence)

3. 순환 복잡도 (Cyclomatic Complexity) = 맥케이브 순환도(McCabe's Cyclomatic) = 맥케이브 복잡도 매트릭(McCabe's Complexity Metrics)

• 프로그램의 논리적인 복잡도를 측정하기 위한 소프트웨어의 척도
• 제어 흐름도 이론에 기초를 둠
• 순환 복잡도를 이용해 계산된 값은 프로그램의 독립적인 경로의 수를 정의하고, 모든 경로가 한 번 이상 수행되었음을 보장하기 위해 행해지는 테스트 횟수의 상한선을 제공
• 제어 흐름도(G)에서 순환 복잡도 V(G) = E - N + 2 (E: 화살표 수, N: 노드 수)

[그림 1] 순환복잡도

 

 

📖 Reference

2023 시나공 정보처리기사 필기 : 네이버 도서