시간복잡도, 공간복잡도
시간복잡도?
1초 = 3-5억개의 연산 (대략 1억개의 연산으로 보는 사람도 많다)
고로 시간제한이 1초라면 당신의 프로그램은 3-5억개의 연산을 처리하고 종료되어야 한다는 뜻
아래의 메서드에서 몇번 연산이 필요한지 알아보자.
function func(int arr[], int n) {
int cnt = 0;
// int cnt를 선언하는데 연산 1번
// 0을 넣는 연산 1번
for(int i=0; i<n; i++){
// n번에 걸쳐 반복되는데 n보다 작은지 연산 1번
// i에 1을 더해주는 연산 1번
if(arr[i] % 5 == 0) cnt++;
// 5로 나눈 나머지를 확인할때 연산 1번
// 0과 일치하는지 확인할 때 연산 1번
// 5의 배수면 cnt를 1증가시켜야하니 연산 1번
}
return cnt;
// cnt를 반환해야 하니 연산 1번
}1 + 1 + n * (2 + 2+ 1) + 1 = 5n + 3
만약 n이 100만이였으면 500만 정도 연산이 필요하니 1초안에 연산이 가능할테고 10억이였으면 대략 50억정도 연산이 필요하니 1초안에 연산이 불가능하다.
보통 시간 복잡도를 말할 때 상수는 떼고 5n + 3를 n에 비례한다고 말한다.
몇가지 문제를 풀어보자.
문제
대회장에 N명의 사람들이 일렬로 서있다. 거기서 당신은 이름이 '가나다'인 사람을 찾기 위해
사람들에게 이름을 물어볼 것이다. 이름을 물어보고 대답을 듣는데까지 1초가 걸린다면
얼마만큼의 시간이 필요할까?
: 앞에서 부터 차례대로 물어보면 된다. 최악의 경우 N초, 최선의 경우 1초,
평균적으로 N/2초가 필요하다. 걸리는 시간은 N에 비례한다.
문제
대회장에 N명의 사람들이 일렬로 서있다. 거기서 당신은 이름이 '가나다'인 사람을 찾기 위해
사람들에게 이름을 물어볼 것이다. 이 때 사람들은 이름 순으로 서있다.
이름을 물어보고 대답을 듣는데까지 1초가 걸린다면
얼마만큼의 시간이 필요할까?
: 업다운게임 하듯이 중간 사람에게 계속 물어보면 된다. 최선의 경우 1초, 최악의 경우 logN초,
평균적으로 logN초가 필요하다. 걸리는 시간은 logN에 비례한다.
(16명이면 4번, 32명이면 5번, 64명이면 6번...)
로그 log ?
코테에는 밑이 다 2인 로그만 나오므로 해당 수가 2의 몇 제곱인지 의미함
log2 = 1, log4 = 2, log8= 3, log16 = 4, log32 = 5, log64 = 6 ...
시간 복잡도(Time Complexity)
입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계
박오표기법(Big O Notation)
주어진 식을 값이 가장 큰 대표향만 남겨서 나타내는 방법
O(N), O(N제곱), O(1)..
O(NlogN) = NlogN + 30N + 10
시간복잡도 그래프
O(1) < O(logN) < O(N) < O(NlogN) < O(N2제곱) < O(2n제곱) < O(N!)
O(1) : 상수시간
O(logN) : 선형시간
O(N) : 선형시간
O(logN), O(NlogN), O(N2제곱), O(2n제곱), O(N!) : 다항시간
O(2n제곱)으로 푼 풀이는 시간제한을 통과하기 힘들 것
시간복잡도 예제
문제 1. N이하의 자연수 중에서 3의 배수이거나 5의 배수인 수를 모두 합한 값을 반환하는 함수 func(int N)을 작성하라. N은 10만 이하의 자연수이다.
function func(N) {
let sum = 0;
for(let i=0; i <= N; i++) {
if(i % 3 === 0 || i % 5 === 0) {
sum += i;
}
}
return sum;
}
console.log(func(16));
시간복잡도 : O(N)
문제2. 주어진 길이 N의 int배열 arr에서 합이 100인 서로 다른 위치의 두 원소가 존재하면 1을,
존재하지 않으면 0을 반환하는 함수 func(int arr[], int N)을 작성하라.
arr의 각 수는 0이상 100이하이고 N은 1000이하이다.
function func(arr, len) {
for(let i=0; i < len; i++) {
for(let j=i+1; j < len; j++){
if(arr[i] + arr[j] === 100) {
return 1;
}
}
}
return 0;
}
console.log(func([1, 52, 48], 3))
console.log(func([50, 42], 2))
console.log(func([4, 13, 63, 87], 4))
시간복잡도 : O(N^2)
문제3. N이 제곱수이면 1을 반환하고 제곱수가 아니면 0을 반환하는 함수 func(int N)을 작성하라.
N은 10억 이하의 자연수이다.
function func(n) {
if(Number.isInteger(Math.sqrt(n))){
return 1;
}
return 0;
}
console.log(func(9));
console.log(func(693953651));
console.log(func(756580036));
// 강사 코드
function func(N) {
for(let i=0; i*i <= N; i++){
if(i*i == N) return 1;
}
return 0;
}
console.log(func(9));
console.log(func(693953651));
console.log(func(756580036));
시간복잡도 : O(루트N)
문제 4. N이하의 수 중에서 가장 큰 2의 거듭제급수를 반환하는 함수 func(int N)을 작성하라.
N은 10억 이하의 자연수이다.
function func(N) {
let value = 1;
while(2 * value <= N){
value *= 2;
}
return value;
}
console.log(func(5))
console.log(func(97615282))
console.log(func(1026))
시간복잡도 : O(logN)
공간복잡도
입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계
메모리 제한이 512MB일 때, int 변수를 대략 1.2억개 사용 가능
Reference