시간복잡도(BIG-O표기법)
우리가 코드를 짤 때 (자료구조 + 알고리즘)을 이용하여 만들 것이다.
그 코드는 다양한 크기로 입력될 것이고
그 코드를 누군가와 공유를 하는 상황이 올 수 있다.
여기서부터 문제가 시작된다.
내가 가지고 있는 컴퓨터와 상대방이 가지고 있는 컴퓨터가 사양이 다른 것이다.
그러면 각자 다른 사양으로 인해 작업속도의 차이가 나기 시작하면서 불편함이 시작된다.
그래서 우리는 시간의 개념을 다르게 잡기로 했다..
빠르다 느리다를 시간으로 즉, 초로 표현하지 않는 것이다.
간단히 말하자면 "완료까지 걸리는 절차의 수"라고 할 수 있다.
실행시간( Running Time = 함수/ 알고리즘 수행에 필요한 스텝의 수
그럼 바로 문제로 들어가보자, 이 함수의 실행시간이 얼마나 될 것인가?
int[] multiply(int[] input, int multiplier) {
int[] nums = new int[input.length]; ---------------1
for(int i = 0; i < input.length; i++) { ---------------2
nums[i] = inputs[i] * multiplier; ---------------3
}
return nums; ---------------4
}식을 세우기 위해 필요한 줄은 보다시피 총 4줄 = 스텝수가 4줄 인 것이다.
그럼 컴퓨터가 이 코드를 실행하기 위해 계산하는 횟수를 계산해 보자.
- 첫 번째 줄(c1) = 1번 ( 입력을 하는 줄이라서 여러 번 할 필요가 없다.)
- 두 번째 줄(c2) = N+1번 ( 반복문으로써 N번 반복하고 마지막으로 빠져나오기 위해 한 번 더 진행한다.)
- 세 번째 줄(c3) = N번 ( 반복문의 N번이 여기서 루프로 돌아간다.
- 네 번째 줄(c4) = 1번 ( 결과물이 나왔고 이것은 한 번만 읽게 될 것이다.)
● 이것은 각각의 줄과 그 줄이 몇번 실행되는지 곱한다. 그리고 그 곱한 것들을 더해주는것이다.
● 그리고 N은 size of input이다.
T(N) = c1 + c2*(N+1) + c3*N + 1
= (c2 + c3)+N + c1 + c2 + 1
a = (c2 + c3)
b = c1 + c2 + 1
= a*N + b
여기서 우리는 N이 무한대로 커지면 실행시간이 과연 얼마나 될 것 이냐가 궁금한것이다.
- N이 커질수록 덜 중요한 것은 제거
- 최고차항만 남긴다.
- 최고 차항의 계수(상수)는 생략한다.
- Big-O(최고 차항) == 결국 위의 코드는 Big-O표기법으로 O(N)이 되는것이다.
우리가 한 이 분석이 점근적 분석이라고 한다.
점근적 표기법은 θ(N)이라고 한다
시간 복잡도
함수의 실행 시간을 표현하는것
주로 점근적 분석을 통해 실행시간을 단순하게 표현을 하며
이때 점근적 표기법으로 표현함
만약 흥미가 생겼다면 조금만 더 들어가보자
이 코드를 예로 들어 조금만 더 알아보자
boolean exists(int[] inputs, int target) {
for (int i = 0; i < inputs.length; i++) {
if(inputs[i] == target) {
return true;
}
}
}
천천히 생각해보자 이 코드는 target이 배열의 어디 있는지 찾는 코드이다.
target의 숫자가 배열의 앞에 있을때와 한참 뒤에 있을때가 있지않을까?
그럼 수행시간을 어떻게 확인할까?
가장 앞에 있다면?(Best) = 1번만에 찾을것이고
가장 뒤에 있거나 없다면?(Worst) = N번안에 알아낼것이다.
그럼 두가지의 수행시간이 차이가 날 텐데
이것을 두가지로 나타내면
Best 점근적 표기법 = Ω(1)
lower bound (하한선)
함수 실행 시간은 아무리 빨라도 상수 시간 이상이다.
Worst 점근적 표기법 = O(N)
upper bound (상한선)
함수 실행 시간은 아무리 오래걸려도 N에 비례하는 정도 이하입니다.
이것이 우리가 점근적 표기법으로 나타낼수있는 시간복잡도의 표기법이다.
그러면 우리는 점근적 표기법을 3가지로 볼수있다.
- θ(N) = tight bound
- Ω(N) = lower bound
- O(N) = upper bound
case별로 표기하자면
| Best(최단시간) | Worst(최장시간) | Average(일반시간) | |
| Ω ( lower bound) | Ω(1) | Ω(N) | |
| O ( upper bound) | O(1) | O(N) | O(N) |
| θ ( tight bound) | θ(1) | θ(N) |
tight bound에 대해서 말하자면
lower bound와 upper bound의 표기법이 모두 같을때 상한선과 하한선이 모두 같을때 thight bound를 사용하는것이다.
혹시나 이것을 사용한다면 상한선과 하한선을 모두 알려주는 역할까지 해줄수 있는것이다.
여기서 upper bound 가 우리가 찾는 Big-O표기법이다.
우리는 기본적으로 최선의 상황보다 최악의 상황을 우려하기 때문에 Big-O를 많이 사용한다.
Binary sourch
이미 정렬이 된 배열을 input으로 받은 상태에서 원하는 target을 찾는것이다.
binary는 처음부터 찾는것이 아니라 반을 쪼개서 그중 가까운곳으로 또 반을 쪼개서 찾는것이다.
배열은 1~100까지 10단위로 정렬되어있는 상태이고 그중 우리는 105를 찾고 싶다.
즉, worst case = 찾는게 없다.
1차 70 , 2차 110, 3차 90, 4차 100 하지만 배열안에는 원하는 숫자가 없었다.
이것은 실행할때마다 1/2만큼 줄어들고 1로 가기까지 얼마나 걸리는가.
(k는 나눈 횟수)
N*(1/2)k=1 -- N = 2k -- log2N = k
즉 , K = log2N
시간복잡도 = θ(logN)이 되는것이다.
이번엔 한번에 찾았을때이다.
즉, best case에 해당되는것이다.
간단하다. θ(1)이 된다.
여기서도 Binary sourch의 best와 worst가 같기 때문에 "θ"를 사용해 주는것이다.
자! 이제 문제를 풀어보자 ( 우리는 생각하기 쉽게 Big-O 표기법으로 문제를 풀자)
void prints(int[] inputs) {
for(int i = 0; i < inputs.length; i++) {
for(int j = 0; j < inputs.length; j++) {
System.out.println("어렵다");
}
}
}간단하다 우리는 상수는 모두 제외하고 반복되는 N의 차수만을 볼것이다.
2중 반복문으로서 N을 N번 반복하면서 N*N을 하는것이다.
우리는 차수만을 볼것이기 때문에 O(N2)이 되는것이다.
void prints(int[] inputA, int[] inputB) {
for(int i = 0; i < inputA.length; i++) {
System.out.println("안녕하세요");
}
for (int i = 0; i < inputB.length; i++) {
System.out.println("반갑습니다");
}
}이것은 두가지의 input이 들어와있다. 즉 N과 M이 들어와있는 상태라고 보면 된다.
그래서 표기법은 O(N+M)이라고 표현한다. 근데 컴퓨터는 그중 더 큰 값을 입력받을것이다.
정확히는 O(max(N,M))이랑 O(N+M)동일한 표기방법이다.
void prints(int[] inputA, int[] inputB) {
for(int i = 0; i <inputA.length; i++) {
for(int j = 0; j < inputB.length; j++) {
System.out.println("힘내세요")
}
}
}마지막으로 이것은 N과 M으로 이중 반복문으로 돌린것이다.
각각의 paremeter가 다르기때문에 각자의 반복문이 다르기 때문에 따로 잡는다.
이건 O(N*M)으로 표현하면 된다.
마지막으로 속도를 비교하고 끝내도록 하겠다. 순으로 점점 느려진다.
O(1) < O(logN) < O(N) < O(N*logN) < O(N2) < O(2N) < O(N!)