0strich
[Data Structure] 시간 복잡도 (Time Complexity) 본문
알고리즘 분석
알고리즘을 분석할 때는 다음의 세 가지 경우로 나눌 수 있다. 최악, 최선, 평균 의 경우
최악의 경우(Worst case)
프로그램이 실행시간의 상한을 계산한다.
프로그램이 실행될 때 연산이 수행되는 횟수가 최대가 되는 경우이다.
배열을 예로 들었을 때 탐색하려는 원소가 없거나 맨 끝에 위치한 경우이다.
최선의 경우(Best case)
프로그램 실행시간의 하한을 계산한다.
프로그램이 실행될 때 연산이 수행되는 횟수가 최소가 되는 경우이다.
배열을 예로 들었을 때 탐색하려는 원소가 맨 앞에 위치한 경우이다.
평균(Average case)
가능한 모든 입력(N)에 대한 실행 시간을 계산한 후, 모든 시간을 더한다.
더한 결과를 입력한 수(N)로 나눈다.
알고리즘 평가
알고리즘 평가하는 데 있어서 실행시간(연산 횟수)과 메모리 사용량을 평가기준으로 나눔
수행 시간(연산 횟수) : 시간 복잡도(Time Complexity)
메모리 사용량 : 공간 복잡도(Space Complexity)
시간 복잡도
시간 복잡도의 정의는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화한 것이다.
쉽게 풀이하자면 알고리즘이 문제를 해결하기 위한 연산의 횟수이다.
함수를 실행했을 때 함수의 수행 시간이 아닌 연산의 횟수를 센다.
알고리즘의 시간 복잡도는 주로 빅-오 표기법으로 나타낸다.
Big-O 표기법
계수와 낮은 차수의 항을 제외시키는 방법
f(n) | Name |
1 | Constant |
log n | Logarithmic |
n | Linear |
n log n | Log Linear |
n ^ 2 | Quadratic |
n ^ 3 | Cubic |
C ^ n | Exponential |
성능 비교
O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^2) < O(2^n)
O(1) : Constant
알고리즘의 문제를 해결하는데 한 단계만 거침
값을 검색할 때 객체의 키를 알거나, 배열의 인덱스를 알고 있다면 언제나 한 단계만 걸림
1 ~ N까지의 합을 구하는 알고리즘을 구하기 위해 다음과 같은 공식을 사용할 수 있다.
공식 : N * (N+1) / 2
var N = 10
var sum = N * (N+1) / 2
sum // 55
반복문을 사용해 하나씩 모두 더하는 알고리즘은 아래의 O(n)이다
O(log N) : Logarithmic
문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듦
ex, 효율 좋은 검색 알고리즘, 트리구조
O(N) : Linear
문제를 해결하기 위한 단계의 수와 입력받은 값 n 이 1:1의 관계를 가짐
1부터 N까지의 합을 구하기 위해 반복문을 사용해서 더하는 알고리즘 또한 구현할 수 있을 것이다.
var N = 10
var sum = 0
var count = 0
for(let i=1; i<=N; i++){
sum += i
count += 1
}
sum // 55
count // 10
1부터 10까지의 합을 구하는데 총 10번의 연산을 하였다
O(N log N) : Log Linear
ex, 효율 좋은 정렬 알고리즘
O(N^2) : Quadratic
문제 해결을 위한 단계의 수는 입력받은 값 n의 제곱
ex, 이중 루프
O(N^3) : Cubic
문제 해결을 위한 단계의 수는 입력받은 값 n의 세제곱
ex, 삼중 루프
O(C^N) : Exponential
문제 해결을 위한 단계의 수는 주어진 상수값 C의 n 제곱
그래프 시간 복잡도
자료구조 시간 복잡도
'Front End > Data Structure' 카테고리의 다른 글
[Data Structure] 그래프 (Graph) (0) | 2020.01.05 |
---|---|
[Data Structure] Stack & Queue (0) | 2019.12.28 |