복잡도

clay·2023년 2월 13일

소프트웨어 개발

목록 보기

31/47

복잡도(Complexity)는 시스템이나 시스템 구성 요소 또는 소프트웨어의 복잡한 정도를 나타내는 말로, 시스템 또는 소프트웨어를 어느 정도의 수준까지 테스트해야 하는지 또는 개발하는데 어느 정도의 자원이 소요되는지 예측하는데 사용된다.

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

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

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

빅오 표기법(Big-O Notation)

알고리즘의 실행시간이 최악일 떄를 표기하는 방법이다.

입력값에 대해 알고리즘을 수행했을 때 명령어의 실행 횟수는 어떠한 경우에도 표기 수치보다 많을 수 없다.

세타 표기법

알고리즘의 실행시간이 평균일 때는 표기하는 방법이다.

입력값에 대해 알고리즘을 수행했을 때 명령어 실행 횟수의 평균적인 수치를 표기한다.

오메가 표기법

알고리즘의 실행시간의 최상일 때를 표기하는 방법이다.

입력값에 대해 알고리즘을 수행했을 때 명령어의 실행 횟수는 어떠한 경우에도 표기 수치보다 적을 수 없다.

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

O(1)

입력값(n)에 관계 없이 일정하게 문제 해결에 하나의 단계만을 거친다.

예) 스택의 삽입(Push), 삭제(Pop)

O(log₂n)

문제 해결에 필요한 단계가 입력값(n) 또는 조건에 의해 감소한다.

예) 이진 트리(Binary Tree), 이진 검색(Binary Search)

O(n)

문제 해결에 필요한 단계가 입력값(n)과 1:1 관계를 가진다.

예) forans

O(nlog₂n)

문제 해결에 필요한 단계가 n(log₂n)번만큼 수행된다.

예) 힙 정렬, 2-way 합병 정렬

O(n²)

문제 해결에 필요한 단계가 입력값(n)의 제곱만큼 수행된다.

예) 삽입 정렬, 쉘 정렬, 선택 정렬, 버블 정렬

O(2ⁿ)

문제 해결에 필요한 단계가 2의 입력값(n) 제곱만큼 수행된다.

예) 피보나치 수열

순환 복잡도(Cyclomatic Complexity)는 한 프로그램의 논리적인 복잡도를 측정하기위한 소프트웨어의 척도로, 맥케이브 순환도 또는 멕케이브 복잡도 메트릭이라고도 하며, 제어 흐름도 이론에 기초를 둔다.

순환 복잡도를 이용하여 계산된 값은 프로그램의 독립적인 경로의 수를 정의하고, 모든 경로가 한 번 이상 수행되었음을 보장하기 위해 행해지는 테스트 횟수의 상한선을 제공한다.
제어 흐름도 G에서 순환 복잡도 V(G)는 다음과 같은 방법으로 계산할 수 있다.

1️⃣ 순환 복잡도는 제어 흐름도의 영역 수와 일치하므로 영역 수를 계산한다.
2️⃣ V(G) = E - N + 2 : E는 화살표 수, N은 노드의 수

샤코타임 팬