시간복잡도(Time Complexity) & 공간복잡도(Space Complexity)

시간복잡도(Time Complexity)

: 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계로 ‘얼마나 오랜 시간’이 걸리는지를 나타내는 데 쓰인다. 보통 시간복잡도는 빅오표기법으로 나타냄

빅오표기법

: 입력 범위 n을 기준으로해서 로직이 몇 번 반복되는지 나타낸다.

예를 들어 시간복잡도 10n^2 + n 을 빅오표기법으로 나타내면 O(n^2)이 된다.

이처럼 연산횟수가 다항식으로 표현될 경우, 최고차항을 제외한 모든 항과, 최고차항의 계수를 제외시켜 나타낸다.

빅오표기법의 종류

1. O(1)
2. O(n)
3. O(log n)
4. O(n^2)
5. O(2^n)

• O(1) : 입력값에 상관없이 즉시 출력값을 얻어낼 수 있다. 예) 인덱스로 배열에 접근할 때, 배열의 크기에 상관없이 시간복잡도가 동일하게 유지된다.

  int[] arr = {1,2,3,4};
  System.out.println(arr[0]); // 배열의 인덱스로 값 접근

• O(n) : 선형 복잡도라고 부르며 입력값이 증가함에 따라 처리시간 또한 같은 비율로 증가한다. 예) n의 크기에 비례하게 증가하는 경우

  for(int i=0;i<n;i++){
  	System.out.println(i); 
  }

• O(logn) : 로그복잡도라고 부른다. 입력값이 증가함에 따라 연산 횟수가 logN에 비례하여 증가한다.

  예) 이진탐색트리(Binary Search Tree)

  예를들어 이진탐색트리를 이용해서 M개의 값 중 원하는 값을 찾는다고 할 때, 루트노드에서 첫번째 자식 노드로 이동하게 되면 탐색 대상이 m/2인 절반으로 줄어들게 된다. 여기서 또 다시 한번 자식 노드 층으로 넘어가게 되면 m/4개의 값이 남게되며 매번 층을 내려갈 때마다 남은 값의 수들이 절반으로 줄어듦. 따라서 탐색해야하는 데이터의 수가 2^n개라고 할 때, 이진탐색트리를 이용할 경우 n번만의 탐색할 수 있기에 시간복잡도는 O(logn)이 된다.

• O(n^2) : 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.

  예) for문이 중첩되어 있는 경우

  for(int i=0;i<n;i++){
  		for(int j=0;j<n;j++){
  				
  		}
  }

• O(2^n) : 입력값의 증가에 따라 연산횟수가 2^n에 비례하여 증가한다.

  대표적으로 재귀를 이용한 피보나치 수열이 O(2^n)의 시간복잡도를 가진다.

  예) 피보나치 수열 → 매번 함수를 호출할 때마다 두번씩 재귀로 함수를 호출한다.

  public int fibo(int n){
  		if(n <= 1) return n;
  		return fibo(n-1) + fibo(n-2);
  }

시간복잡도가 존재하는 이유 ?

시간복잡도는 효율적인 코드로 개선하는 데 쓰이는 척도가 된다.

O(n^2)의 시간복잡도가 9초가 걸린다고 했을 때 이를 O(n)의 시간복잡도로 개선하게 된다면 9초→3초로 시간을 줄일 수 있다.

공간복잡도(Space Complexity)

: 공간 복잡도는 프로그램을 실행시켰을 때 필요로하는 자원 공간의 양을 뜻한다.

예를들면 int a[1004] 라는 배열이 있다고 했을 때 해당 배열은 1004*4바이트 크기를 가지게 된다.