시간 복잡도(Time Complexity)
- 알고리즘을 수행하기 위해 프로세스가 수행해야하는 명령어의 실행 횟수(연산 횟수)를 수치화 한것
- 왜 실행시간이 아닌 연산수치로 판별할까? 명령어의 실행시간은 컴퓨터의 하드웨어 또는 프로그래밍 언어에 따라 편차가 크게 달라지기 때문에 명령어의 실행 횟수만을 고려하는 것이다.
Big-O 표기법
- 시간 복잡도를 표기하는 방법
- 실행 시간 n을 O(n)으로 표기
- Big-O에서 차수가 가장 높은 최고차항만 두고 나머지는 버림
- 1) O(1) - Constant Time
- 입력되는 데이터양과 상관없이 일정한 실행 시간을 가진다.
- 문제를 해결하는데 오직 한 단계만 처리함.
- 2) O(log n) - Binary search tree access(이진 검색) - search(검색), insertion(삽입), deletion(삭제)
- 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬.
- 만약 입력 자료의 수에 따라 실행 시간이 이 log N의 관계를 만족한다면 N이 증가함에 따라 실행시간이 조금씩 늘어난다. 주로 커다란 문제를 일정한 크기를 갖는 작은 문제로 쪼갤때 나타나는 유형이다.
- 3) O(n) - Linear Time
- 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐.(입력데이터양에 따른 정비례 관계)
- Linear search, for 문을 통한 탐색을 생각하면 된다.(단일 Loop)
- 4) O(n log n)
- 문제를 해결하기 위한 단계의 수가 N*(log2N) 번만큼의 수행시간을 가진다.
- 5) O(n^2) - Quadratic Time
- 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱(효율이 좋지 않음, 사용 X)
- 해당 유형은 이중 Loop내에서 입력 자료를 처리 하는 경우
- 6) O(C^n)
- 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱.
시간복잡도를 사용하는 이유
- 수행시간을 통해 시간복잡도를 구하고 효율적인 알고리즘인지 분석하기 위해
각 자료구조 별 시간 복잡도
각 알고리즘 별 시간 복잡도
