복잡도

복잡도(Complexity)는 말 그대로 복잡한 정도를 나타내는 말이다. 시스템이나 소프트웨어를 어느정도까지 테스트 해야하는지 혹은 개발하는데 어느정도의 자원이 소요되는지 예측하는데 사용된다.

걸리는 시간이 중요하게 여겨져, 시간의 복잡도가 중요하다.

어느정도의 자원이 소요되는지 예측하는데 사용된다.

시스템의 복잡도가 높으면 장애가 발생할 수 있으므로 정밀한 테스트를 통해 미리 오류를 제거 할 필요가 있다.

시간복잡도

시간 복잡도는 알고리즘의 실행시간, 알고리즘을 수행하기 위해 수행하는 연산 횟수를 수치화 한 것을 의미한다.

시간 복잡도가 낮을 수록 알고리즘의 실행 시간이 짧고, 높을 수록 실행시간이 길어진다.

하드웨어 성능이나 프로그래밍 언어에 따라 알고리즘의 실행시간이 달라 명령어의 실행 횟수를 표기하는데, 이를 점근 표기법이라 한다. 빅오표기법, 세타표기법, 오메가 표기법이 있으나 세타는 평가하기 까다롭고 오멕는 신뢰성이 떨어져 이들에 비해 성능 예측하는데 용이해 빅오 표기법을 주로 사용한다.

빅오표기법(Big-O Notation) 알고리즘 실행시간이 최악일때를 표기한다. 최악의 실행횟수를 표기하므로 이보다 더 큰 수치가 나올 수 없다.

O(1)	입력값에 관계없이 일정하게 문제해결에 하나의 단계만을 거친다. ex)스택의 삽입,삭제
O(log 2 n)	입력값 또는 조건에 의해 문제 해결에 필요한 단계가 감소한다. ex) 이진트리(binary tree),이진 검색(binary search)
O(n)	문제 해결에 필요한 단계가 n과 1대 1의 관계를 가진다. ex) for문
O(nlog 2 n)	문제 해결에 필요한 단계가 n(log2n)번만큼 수행된다. ex)힙정렬(heap sort),2-way합병정렬(merge-sort)
O(n²)	필요한 단계가 입력값(n)의 제곱만큼 수행 ex)삽입정렬(insertion sort),쉘정렬(shell sort),선택정렬(selection sort),버블정렬(bubble sort),퀵정렬(quick sort)
O(2^n)	문제 해결에 필요한 단계가 2의 입력값(n)제곱만큼 수행한다. ex)피보나치 수열