시간복잡도

시간복잡도

Time Complexity
●시간 복잡도를 이용하면 작성한 코드가 시간이 대략 얼마나 걸릴지 예상할 수 있다.
●표기법으로 대문자 O를 사용한다. (다양한 시간 복잡도가 많지만, 보통 Big-O만 사용한다.)
●영어로는 Big O Notation
●Big O Notation에서 상수는 버린다.
●두 가지 항이 있을 때, 변수가 같으면 큰 것만 빼고 다 버린다.
●입력의 크기 N에 대해서 시간이 얼마나 걸릴지 나타내는 방법
즉, 최악의 경우에 시간이 얼마나 걸릴지 알 수 있다.
●시간복잡도는 소스를 보고 계산할 수 있도 있고, 소스를 작성하기 전에 먼저 계산해볼 수 있다.
●문제를 풀기 전에 먼저 생각한 방법의 시간 복잡도를 계산해보고 이게 시간 안에 수행될 것 같은 경우에만 구현하는 것이 좋다.

시간복잡도예시

총 N명의 사람이 식당에 방문했다.
식당에는 메뉴가 M가 있고, 메뉴판이 1개 있다.
사람 1명이 메뉴판을 읽는데 걸리는 시간은 O(M)이다.
주문한 모든 메뉴는 동시에 나왔고, 각 사람 i가 식사를 하는데 걸리는 시간은 $A_{i}$이다.
각 사람이 계산을 하는데 걸리는 시간은 O(P)이다.

각 사람이 메뉴판에 있는 모든 메뉴를 읽는 시간 복잡도는 O(NM)
모든 사람이 식사를 마치는데 걸리는 시간 = O(max($A_{i}$))
식사를 모두 마친 다음 한 줄로 서서 각자 계산을 하는 시간 복잡도는 = O(NP)

N번 O(N)

int sum = 0;
for(int i =1; i<=N; i++){
	sum += i;
}

$O(N^2)$

int sum =0;
for(int i=1; i<N; i++){
	for(int j=1; j<=N; j++){
    	if(i==j){
        	sum += j;
        }
    }
}

O(1)

int sum = 0;
sum = N*(N+1)/2;

O(1)
O(N)
$O(N^2)$
여기에 값을 넣었을때 1억이 나오면 보통 1초 나온다고 본다.
N=<10만
O(1) =>1
O(N) => 10만
$O(N^2)$ => 100억 /100초

메모리

●보통 가장 많은 공간을 사용하는 것은 보통 배열이다.
●배열이 사용한 공간: 배열의 크기 X 자료형의 크기 B
●보통 배열의 크기가 크면 시간 초과를 받는 경우가 많다.
●불필요한 공간이 없다면, 대부분 메모리 제한은 알아서 지켜진다.

입/출력

JAVA
●Java는 입력은 Scanner, 출력은 System.out을 사용한다.
●Scanner sc = new Scanner(System.in);
●입력이 많은 경우에는 속도가 느리기 때문에, BufferedReader를 사용한다.
●BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
●출력이 많은 경우에는 StringBuilder를 사용해서 한 문자열로 만들어서 출력을 한 번만 사용하거나 BufferedWrtier를 사용한다.