선형식은 언젠가 상수를 뛰어넘게 된다.
- 예를 들어 파일의 크기에 따라 전송시간이 증가한다면
선형시간으로 증가한다고 볼 수 있다. - 반면에 파일의 크기와는 상관없이 일정한 전송시간을 가진다면
상수시간을 가진다고 볼 수 있다. - 실행 시간에는 다양한 변수가 포함 될 수 있다
big-o
- 시간의 상한을 나타낸다.
- 이것은 작거나 같은 부등호와 비슷한 관계가 있다.
- 예를들어 김잼민의 나이가 X살 이라고 하고, 사람의 최대 수명이 130살이라고 하자.
- 이것은
X <= 130으로 표현 할 수 있지만 X <= 1000혹은X <= 1000000이라고 표현해도 옳은 표기법이다.
big-omega
- 등가 개념 혹은 하한을 의미한다.
- 알고리즘은 big-omega의 수행시간보다 빠를 수 없다.
big-theta
- big-o이자 big-omega이다.
- 평균값이라고도 할 수 있다.
- 일반적으로 알고리즘 테스트에서 말하는 big-o는 이것에 해당한다.
시간 복잡도를 계산할 때
- 상수항은 무시한다.
- 지배적이지 않은 항은 무시한다.
- A를 모두 마치고 B를 수행한다는 것은
O(A+B)를 의미한다. - A를 할 때마다 B를 수행한다는 것은
O(A*B)를 의미한다.
상환시간
- ArrayList는 원소 삽입 시 필요에 따라 크기를 증가 시킬 수 있다.
- 용량이 가득 찼을 때 기존보다 두배 더 큰 배열을 만들어 이전 배열의 값을 복사한다.
- 이 상황에서 삽입연산의 수행시간은 어떻게 구할 수 있을까.
길이가 N인 배열에 N개의 원소가 있을 때(배열이 가득 찼을 때)는 O(N)이다.
길이가 2N인 배열을 만들고 복사하기 때문이다.
반대로 배열이 가득차지 않았을 때는 그냥 삽입하면 되기 때문에 O(1)이라고 할 수 있다.
배열이 가득 찼을 때 배열의 크기는 2의 거듭제곱이라고 할 수 있다. 이말은 다음처럼 표현 할 수 있다.1 + 2 + 4 + 8 + 16 + 32 + ... + X
이 표현을 살짝 뒤집으면X + X/2 + X/4 + X/8 + ... + 1
이렇게 표현 할 수 있는데 이 값의 합은 약 2X와 같다.
따라서 이런 경우 시간 복잡도는 O(2X)라고 할 수 있다.
logN 수행시간
- 원소 N을 절반 씩 나누는 과정에서 몇 단계 만에 1이 되는지를 본다.
- $$2^4 = 16$$
- $$log_{2}16 = 4$$
- $$log_{2}N = k$$
- $$2^k = N$$
재귀적 수행시간
public int f (int n){
if (n <= 1){
return 1;
}
return f(n-1) + f(n-1);
}
- n이 4일 경우
- 트리의 깊이가 N일 때
- 시간 복잡도는 다음과 같다
- $$O(분기^{깊이})$$
- 여기서 분기란 재귀함수가 자신을 재 호출하는 횟수를 말한다.
- 또한 전체 노드의 수는 다음과 같다
- $$2^{N+1}$$
- 위의 함수에서 적용을 하자면 함수 내에서 재 호출되는 함수는 2개이고 n이 4 일 때 깊이가 3이기 때문에 다음처럼 표시 할 수 있다.
- $$O(2^3)$$