복잡도

1. 복잡도(Complexity)

시스템, 시스템 구성요소, 소프트웨어의 복잡한 정도

 

2. 시간 복잡도

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

 

* 점근 표기법 종류

1) 빅오 표기법(Big-O Notation)

- 알고리즘 실행시간이 최악일 때를 표기하는 방법

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

 

2) 세타 표기법(Big-Θ Notation)

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

- 입력값에 대해 알고리즘 수행 시 명령어 실행 횟수의 평균적인 수치를 표기

 

3) 오메가 표기법(Big-Ω Notation)

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

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

 

3. 빅오 표기법으로 표현한 최악의 알고리즘 시간 복잡도

(1) O(1)

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

ex) stack 삽입, 삭제

 

(2) O(log₂n)

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

ex) 이진 트리, 이진 검색

 

(3) O(n)

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

ex) for문

 

(4) O(nlog₂n)

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

ex) 힙 정렬, 2-Way 합병 정렬

 

(5) O(n²)

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

ex) 삽입 정렬, 쉡 정렬, 선택 정렬, 버블 정렬, 퀵 정렬

 

(6) O(2ⁿ)

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

ex) 피보나치 수열

 

4. 순환 복잡도(Cyclomatic Complexity)

(1) 논리적 복잡도를 측정하기 위한 소프트웨어의 척도

(2) 맥 케이브 순환도 또는 맥케이브 복잡도 메트릭이라고도 함

(3) 제어 흐름도 이론에 기초를 둠

(4) 제어흐름도 G에서 순환복잡도 V(G)는 다음 과 같이 계산, E : 화살표 수, N : 노드 수

V(G) = E - N + 2  

 

 

출처 :  정보처리기사 실기 2024 기본서 / 저자 : 길벗알앤디(김정준, 강윤석, 김용갑, 김우경)  / 출판사 : 길벗