52. 복잡도

복잡도의 개요

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

시간 복잡도

• 시간 복잡도는 알고리즘의 실행시간, 즉 알고리즘을 수행하기 위해 프로세스가 수행하는 연산 횟수를 수치화한 것을 의미한다.
• 시간 복잡도가 낮을수록 알고리즘의 실행시간이 짧고, 높을수록 실행시간이 길어진다.
• 시간 복잡도는 알고리즘의 실행시간이 하드웨어적 성능이나 프로그래밍 언어의 종류에 따라 달라지기 때문에 시간이 아닌 명령어의 실행 횟수를 표기하는데, 이러한 표기법을 점근 표기법이라고 한다.
• 점근 표기법의 종류

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

빅오 표기법(Big-O Notation)

• 빅오 표기법은 알고리즘의 실행시간이 최악일 때를 표기하는 방법으로, 신뢰성이 떨어지는 오메가 표기법이나 평가하기 까다로운 세타 표기법에 비해 성능을 예측하기 용이하여 주로 사용된다.
• 일반적인 알고리즘에 대한 최악의 시간 복잡도를 빅오 표기법으로 표현하면 다음과 같다.
  • O(1): 입력값에 관계 없이 일정하게 문제 해결에 하나의 단계만을 거친다.(스택의 삽입(Push), 삭제(Pop))
  • O($log_2n$): 문제 해결에 필요한 단계가 입력값(n) 또는 조건에 의해 감소한다.(이진 트리(Binary Tree), 이진검색(Binary Search))
  • O(n): 문제 해결에 필요한 단계가 입력값과의 관계를 가진다.(for문)
  • O($nlog_2n$): 문제 해결에 필요한 단계가 nllogan)번만큼 수행된다.(힙 정렬(Heap Sort), 2-Way 합병 정렬(Merge Sort))
  • O($n^2$): 문제 해결에 필요한 단계가 입력값(n)의 제곱만큼 수행된다.(삽입 정렬(Insertion Sort), 쉘 정렬(Shell Sort), 선택 정렬(Selection Sort), 버블 정렬 (Bubble Sort), 퀵 정렬(Quick Sort))
  • 0($2^n$): 문제 해결에 필요한 단계가 2의 입력값(n) 제곱만큼 수행된다.(피보나치 수열(Fibonacci Sequence))

순환 복잡도

• 순환 복잡도(Cyclomatic Complexity)는 한 프로그램의 논리적인 복잡도를 측정하기 위한 소프트웨어의 척도로, 맥케이브 순환도(McCabe's Cyclomatic) 또는 맥케이브 복잡도 메트릭(McCabe's Complexity Metrics)라고도 하며, 제어 흐름도 이론에 기초를 둔다.
• 순환 복잡도를 이용하여 계산된 값은 프로그램의 독립적인 경로의 수를 정의하고, 모든 경로가 한 번 이상 수행되었음을 보장하기 위해 행해지는 테스트 횟수의 상한선을 제공한다.
• 제어 흐름도 G에서 순환 복잡도 V(G)는 다음과 같은 방법으로 계산할 수 있다.
  • 방법 1
    • 순환 복잡도는 제어 흐름도의 영역 수와 일치하므로 영역 수를 계산한다.
  • 방법 2
    - V(G)= E - N + 2: E는 화살표 수, N은 노드의 수
    

출처: 2024 시나공 정보처리기사 필기 기본서