복잡도
💡 순환복잡도 계산
💡 빅오 표기법 종류, 예시
¹ 복잡도의 개요
🖍️ 복잡도 Complexity
시스템이나 시스템 구성 요소 또는 소프트웨어의 복잡한 정도
- 시스템/소프트웨어를 어느 정도의 수준까지 테스트해야하는지
개발하는데 어느 정도의 자원이 소요되는지 예측하는데 사용
- 복잡도가 높으면 장애가 발생할 수 있으므로 정밀한 테스트를 통해 미리 오류를 제거할 필요가 있음
² 시간 복잡도
🖍️ 알고리즘의 실행시간, 즉 알고리즘을 수행하기 위해 프로세스가 수행하는 연산 횟수를 수치화 한것
- 점근 표기법: 알고리즘의 실행시간이 하드웨어적 성능이나 프로그래밍 언어의 종류에 따라 달라지기 때문에 시간이 아닌 명령어의 실행 횟수를 표기
점근 표기법
- 빅오 표기법: 최악 - 이것보다 나쁠 수 없음
- 세타 표기법: 평균
- 오메가 표기법: 최상 - 이것보다 적을 수 없음
³ 빅오 표기법
🖍️ 신뢰성이 떨어지는 오메가나 세타에 비해 성능을 예측하기 용이하여 주로 사용
- O(1): 스택 push, pop
- O(log₂n): 입력값 또는 조건에 의해 감소, 이진트리, 이진검색
- O(n): for문
- O(nlog₂n): 힙정렬, 2-way 합병정렬
- O(n²): 삽입, 쉘, 선택, 버블, 퀵 정렬
- O(2ⁿ): 피보나치 수열
⁴ 순환 복잡도
🖍️ 한 프로그램의 논리적인 복잡도를 측정하기 위한 소프트웨어의 척도
= 맥케이브 순환도
= 맥케이브 복잡도 메트릭
- 제어 흐름도 이론에 기초를 둠
- 순환 복잡도를 이용하여 계산된 값은 프로그램의 독립적인 경로의 수를 정의
- 모든 경로가 한 번 이상 수행되었음을 보장하기 위해 행해지는 테스트 횟수의 상한선을 제공
순환 복잡도 구하기
화살표 개수 - 노드 개수 + 2
왕왕