알고리즘은,
어떤 목적을 달성하거나 결과물을 만들어 내기 위해 거치는 일련의 과정
효율적으로 프로그래밍 문제를 풀기 위해 사용하는 것이 "시간복잡도"가 낮은 알고리즘을 사용함
입력값이 커짐에 따라서 증가하는 시간비율을 최소화한 알고리즘을 구현하는 것이 목표
알고리즘의 실행시간 = 컴퓨터가 알고리즘 코드를 실행하는 속도
컴퓨터의 처리속도 / 사용자의 언어종류 / 컴파일러의 속도에 따라 달려있음
1) 입력값의 크기에 따라서 알고리즘의 실행시간을 검증
2) 입력값 크기에 따라 함수증가량(성장률)에 집중하는 것 (점근적 표기법 : 오메가 / 세타 / 빅오)
시간 복잡도의 표기법 (빅오 표기법)
1) 오메가 표기법 Big-Ω (최상)
2) 세타 표기법 Big-θ (평균)
3) 빅오 표기법 Big-O (최악) : 불필요한 연산을 제거해 알고리즘 분석을 쉽게 할 수 있도록 사용 (최악고려)
시간복잡도 : 입력된 n의 크기에 따라 실행되는 조작의 수
공간복잡도 : 알고리즘이 실행될 때 사용하는 메모리의 양(데이터 저장의 메모리 발전으로 중요도 낮아짐)
시간복잡도
알고리즘을 수행하기 위해 프로세스가 수행해야 하는 연산을 수치화한 것
"입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?" 를 고려하는 것
명령어의 실행시간은 컴퓨터의 하드에어 or 프로그래밍 언어에 따라 편차가 달라지기 때문에 실행 횟수만 고려
* 시간복잡도의 문제해결 단계 (가장 큰 영향을 미치는 n의 단계)
1 > 0(1) > 상수
2n + 20 > 0(n) > n이 가장 큰 영향을 미침
3n^2 > 0(n^2) > n^2가 가장 큰 영향을 미침
| 시간 | 설명 |
| O(1) | 일정한 복잡도 (constant complexity), 입력값 크기와 관계없이 즉시 출력 가능(시간 증가x) 문제를 해결하는데 한 단계만 처리 |
| O(log n) | 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듦 O는 로그 복잡도(logarithmic complexity) 라 부르고, Big O 표기법 중 O(1) 다음으로 빠른 시간 복잡도를 가짐 BST(노드 이동 시마다 경우의 수가 절반으로 줄어듦, 숫자 맞추기 게임) |
| O(n) | 선형 복잡도 (linear comlpexity), 입력값이 증가함에 따라서 시간도 같은 비율로 증가 문제를 해결하기 위한 단계의 수와 입력값이 n이 1:1 관계를 가짐 하나의 루프를 사용해 단일 요소의 집합을 반복하는 경우 / 절반 이상을 반복 |
| O(n2) | 2차 복잡도, 입력값이 증가함에 따라서 시간이 N의 제곱수 비율로 증가하는 것을 의미 |
| O(2n) | 기하급수적 복잡도, Big-O 표기법중 가장 느린 시간 복잡도를 가짐 (재귀로 구현하는 피보나치) |
| O(n log n) | 문제를 해결하기 위한 단계의 수가 N *(log2N) 번만큼 수행시간을 가짐 |
| O(C^n) | 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱 |
참고
'Algorithm' 카테고리의 다른 글
| 해시테이블 (0) | 2022.10.14 |
|---|---|
| [알고리즘] 문자열 출력 / substr / substring / charAt (1) | 2022.09.26 |
| [알고리즘] 유클리드 호제법 / 최대공약수 (1) | 2022.09.26 |
| [알고리즘] BFS / DFS (1) | 2022.09.23 |
| [알고리즘] Queue / Stack (0) | 2022.09.23 |