[2021 정보처리기사-2과목] #복잡도(빅오 표기법, 순환 복잡도)

목차

 

 

 

 

 

[정보처리기사 2과목 필기 예상 키워드] 목록으로 돌아가기
과목: 2. 소프트웨어 개발 챕터: 4장 어플리케이션 테스트 관리 키워드: 복잡도	#점근표기법(Big-O Notation 등) #빅오 표기법 #순환 복잡도(McCabe's Cyclomatic)

 

 

 

복잡도란?

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

 

 

 

 

시간 복잡도

알고리즘의 실행시간, 즉 알고리즘을 수행하기 위해 프로세스가 수행하는 연산 횟수를 수치화한 것으로 시간이 아닌 명령어의 실행 횟수를 표기하는데 이러한 표기법을 점근 표기법이라 하며 종류는 다음과 같다.

빅오 표기법(Big-O Notation)	알고리즘의 실행시간이 최악일 때를 표기하는 방법(실행 횟수는 어떠한 경우에도 표기 수치보다 많을 수 없다)
세타 표기법(Big-θ Notation)	알고리즘의 실행시간이 평균일 때를 표기하는 방법(실행 횟수는 평균적인 수치). 표기하기 까다로움
오메가 표기법(Big-Ω Notation)	실행시간이 최상일 때를 표기하는 방법(실행 횟수는 어떠한 경우에도 표기 수치보다 적을 수 없다).  신뢰성 떨어짐

 

 

 

 

 

 

빅오 표기법(Big-O Notation)

일반적인 알고리즘에 대한 최악의 시간 복잡도를 표기하면 다음과 같다.

O(1)	입력값(n)에 관계 없이 일정하게 문제 해결에 단 하나의 단계만을 거친다(Push, Pop)
O(log2n)	문제 해결에 필요한 단계가 입력값(n) 또는 조건에 의해 감소(Binary Tree, Binary Search)
O(n)	문제 해결에 필요한 단계가 입력값(n)과 1:1의 관계를 가짐(for)
O(nlog2n)	문제 해결에 필요한 단계가 입력값 n(log2n)번만큼 수행(합 정렬, 합병 정렬)
O(n^2)	문제 해결에 필요한 단계가 입력값(n)의 제곱만큼 수행(삽입, 선택,쉘,버블,퀵)
O(2^n)	문제 해결에 필요한 단계가 2의 입력값(n) 제곱만큼 수행(피보나치)

 

 

 

 

 

정렬(Sort)의 방식에 따른 빅오 표기법 구분

삽입 정렬(Insertion Sort) = O(n^2)
키워드: "이미 순서화된 파일에 n번째 키를 앞의 n-1개의 키와 비교하여 정렬"

쉘 정렬(Shell Sort) = O(n^2)
키워드: "매개변수"

선택정렬(Selection Sort)  = O(n^2)
키워드: "n개의 레코드 중에서 최소값을 찾아 첫 번째 레코드 위치에 놓고 나머지 n-1개 중에 다시 최소값을 찾아 두 번째 레코드 위치에 놓는 방식"

버블 정렬(Bubble Sort) = O(n^2)
키워드: "인접한 두 개의 레코드 값을 비교하여 위치를 서로 교환하는 방식"

퀵 정렬(Quick Sort) = O(n^2)
키워드: "작은 값은 왼 쪽에 큰 값은 오른쪽에 모이도록"

힙 정렬(Heap Sort) = O(nlog2n)
키워드: "전이진 트리(Complete Binary)를 이용한 정렬방식"

2-Way합병정렬(Merge Sort) = O(nlog2n)
키워드: "이미 정렬된 두 개의 파일을 한 개의 파일로 합병"

기수 정렬(Radix Sort)=Bucket Sort
"Queue를 이용하여 자릿수 별로 순서에 맞는 버킷에 분배하였다가 버킷 순서대로 꺼내어 정렬"

 

 

 

순환복잡도

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

*(중요) 제어 흐름도 G에서 순환 복잡도 V(G)는 다음과 같은 방법으로 계산할 수 있다.
1) 순환복잡도=제어 흐름도 영역 수 이므로 영역 수를 센다(외부영역 포함)
2) V(G) = E(화살표) - N(노드) + 2 의 공식을 이용하여 계산한다

 

 

 

 

 

 

 

 

 

---

[2021 정보처리기사 키워드 정리] 2. 소프트웨어 개발 (상시업데이트)

참고: 시나공 정보처리기사 필기 (저자: 강윤석, 김용갑, 김우경, 김정준 | 출판사: 길벗), 유튜브 주간컴공TV