정보처리기사 실기(애플리케이션 테스트 관리) 복잡도

※본 내용은 스스로 공부하며 중요하다고 생각하는 부분만 정리한 내용입니다. 

---

공부 서적(시나공 정보처리기사 필기책)

시나공 정보처리기사 실기

출처: 시나공 정보처리기사 실기

저자: 김정준,강윤석,김용갑,김우경

출판사 : 길벗

---

복잡도

---

 

복잡도

• 시스템 구성 요소 또는 소프트웨어의 복잡도 정도를 나타냄
• 어느 정도 자원이 소요되는지 예측하는데 사용

시간 복잡도

• 알고리즘을 수행하기 위해 프로세스가 수행하는 연산 횟수를 수치화한 것
• 낮을수록 실행시간 짧고 높을수록 실행시간 길어진다.
• 빅오 표기법 : 최악일 때 표기, 실행횟수 가장 많음
• 세타 표기법 : 평균일 때 표기 , 실행횟수 평균적 수치
• 오메가 표기법 : 최상일 때 표기, 실행횟수 가장 적음

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

• O(1) : 문제 해결의 하나의 단계만 거침, 스택의 삽입/삭제
• O(log₂n) : 문제 해결에 필요한 단계가 입력값 또는 조건에 의해 감소, 이진 트리/이진 검색
• O(n) : 입력값과 1:1의 관계, for문
• O(nlog₂n) : 필요한 단계가 n(log₂n)번 수행, 힙 정렬, 2-Way 합병 정렬
• O(n²) : 필요한 단계가 입력값의 제곱만큼 수행, 선택 정렬/버블 정렬/쉘 정렬/삽입 정렬/퀵 정렬
• O(2ⁿ) : 2의 입력값 제곱만큼 수행, 피보나치 수열

순환 복잡도

• 논리적인 복합도를 측정하기 위한 소프트웨어의 척도, 맥케이브 순환도
• 제어 흐롬도의 기초
• E(화살표) - N(노드) + 2 또는 영역의 수