정보처리기사 실기_ 빅오 표기법으로 표현한 시간 복잡도

안녕하세요 jju_developer입니다.

오늘은 대망의 23년 07월 21일 금요일!!

내일은 정보처리기사 실기 시험일입니다.

누가 시험일 전날에 이걸 정리하냐 하지만...

저는 너무 긴장이 되기 때문에 환기를 시킬 겸

블로그 글을 써봅니다...

 

23년 2회 정처기 실기 시험의 난의도가 엄청 어려울 것으로 예상이 되고 있기 때문에

빅오 표기법과 순환 복잡도의 식도 같이 암기를 해 가려고 합니다.

 

그럼 지금부터 시작하겠습니다!

 

우선 복잡도에 대해서 알아보겠습니다.

 

복잡도란?

복잡도(Complexity)는 시스템이나 시스템 구성 요소 또는 소프트웨어의 복잡한 정도를 나타내는 말로,

시스템 또는 소프트웨어를 어느 정도의 수준까지 테스트해야 하는지

또는 개발하는데 어느 정도의 자원이 소요되는지 예측을 해야 하는지에 사용이 됩니다.

시스템의 복잡도가 높으면 장애가 발생할 수 있으므로

정밀한 테스트를 통해 미리미리 오류를 제거할 필요가 있죠.

그렇다면 시간복잡도는?

시간 복잡도란?

우리가 짠 알고리즘을 수행하기 위해서 프로세스가 수행하는

연산의 횟수가 몇 번이 되는지

이 연산 횟수를 수치화한 것이 시간 복잡도입니다.

연산 횟수가 많아지면 당연히 시간도 늘어나겠죠?

표기법의 종류 3가지 알아보겠습니다.

1. 빅오 표기법

빅오 표기법(Big-O Notation)

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

(실행 횟수는 어떠한 경우에도 표기 수치보다 많을 수 없습니다)

 

2. 세타 표기법
세타 표기법(Big-θ Notation)

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

표기하기 까다로운 단점이 있습니다.

(실행 횟수는 평균적인 수치를 의미합니다.) 

 

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

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

신뢰성 떨어진다는 단점이 있습니다.

(실행 횟수는 어떠한 경우에도 표기 수치보다 적을 수 없습니다). 

 이 세 종류 중에서 정보처리 기사에 나오는

빅오 표기법에 대해 더 자세히 알아보겠습니다~

 

🔸 빅오 표기법

빅오 표기법(Big-O Notation)
일반적인 알고리즘에 대한 최악의 시간 복잡도를 표기하면 다음과 같습니다.

1. O(1)

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

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

2. O(log2n)

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

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

조건 즉, 몇 개를 검색을 하느냐에 따라 시간 복잡도가 달라짐!

3. O(n)

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

-> 예시) for문

4. O(nlog2n)

: 문제 해결에 필요한 단계가 입력값 n(log2n)번만큼 수행

-> 예시)  힙 정렬, 2way 합병 정렬 (Heap sort, Merge sort)

5. O(n^2)

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

-> 예시) 삽입, 선택, 쉘, 버블, 퀵 정렬

(insertion short, shall sort, selection sort, bubble sort, quick sort)

입력값이 크면 클수록 제곱을 해서 시간이 많이 걸리겠군!

6. O(2^n)

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

-> 예시) 피보나치

23 정보처리 산업기사 1회 실기시험 문제로 나온 피보나치

자기 자신을 계속 불러서 수행
 

---

예시 정리 참고

정렬(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)라 합니다.

문제에서 McCabe's cyclomatic 수를 구하라고 나오더라고요! 참고 참고!!!

순환 복잡도 계산식

*(중요) 제어 흐름도 G에서 순환 복잡도 V(G)는 다음과 같은 방법으로 계산할 수 있다.

요방법 강추) V(G) = E(화살표) - N(노드) + 2의 공식을 이용하여 계산하면 편리합니다.

 

끝!

이제 진짜 마지막 쓱 정리하고 내일 시험 잘 보고 오겠습니다.

 

모두 파이팅~