복잡도

✨ 알고리즘을 설계하고나면 알고리즘 성능을 분석할 필요가 있다. 이런 알고리즘 효율성을 판단하기 위해 공간 복잡도와 시간 복잡도의 두가지 방법을 이용한다.

시간복잡도
주어진 입력에 따라 알고리즘이 문제를 해결할 때 걸리는 시간. 가장 일반적으로 사용하는 알고리즘 성능 효율 분석 방법.

공간복잡도
알고리즘이 문제를 해결할 때 점유하는 메모리 공간을 뜻함. 자원이 제한된 시스템에서 동작하는 프로그램을 구현하는 것과 같이 특별한 경우에 사용하는 분석 방법.

• 알고리즘을 분석하거나 성능을 측정할 때는 시간 복잡도를 훨씬 더 자주 이용한다.

• 알고리즘의 효율성을 수학적으로 판단하는 방법은 점근적 분석이라고도 한다.
  -> 이 방법의 본질은 수학적으로 알고리즘 성능의 한계를 증명하는 것이므로 실제적인 방법보다 많은 시간을 절약할 수 있기도 하다.

점근적 분석
입력 되는 데이터의 크기에 따라 수행 시간과 공간을 얼마나 차지하는지를 측정

• 효율적인 알고리즘을 구현한다는 것은 바꾸어 말해 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성했다는 이야기이다.

시간 복잡도

빅 오메가, 리틀 오메가, 빅 오, 리틀 오, 세타 등 다양한 표기법이 존재

✨ 참고

• Big-O(빅-오) ⇒ 상한 점근

• Big-Ω(빅-오메가) ⇒ 하한 점근

• Big-θ(빅-세타) ⇒ 그 둘의 평균

• 위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법이다.

점근적 표기법

• 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법

가장 많이 사용되는 표기방법이 빅 오 표기법이다.

✨ Why big O?

• 빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문이다.
• “최소한 특정 시간 이상이 걸린다” 혹은 “이 정도 시간이 걸린다”를 고려하는 것보다 “이 정도 시간까지 걸릴 수 있다”를 고려해야 그에 맞는 대응이 가능하다.

간단하게 알아보는 예제

• 결과를 반환하는 데 최선의 경우 1초, 평균적으로 1분, 최악의 경우 1시간이 걸리는 알고리즘을 구현.

✨ 시간 복잡도 최선의 경우를 고려한 경우

• 알고리즘을 100번 실행시, 최선의 경우 100초가 걸린다
  하지만 실제로 걸린 시간이 1시간을 넘겼다면, '어디서 문제가 발생했나'라는 의문이 생긴다. 최선의 경우만 고려하였으니, 어디에서 문제가 발생했는지 알아내기 위해서는 로직의 많은 부분을 파악해야 하므로 문제를 파악하는 데 많은 시간이 필요하다.

✨ 시간 복잡도 중간의 경우를 고려한 경우

• 평균값을 기대하는 시간 복잡도를 고려한다면 어떨까?
  알고리즘을 100번 실행할 때 100분의 시간이 소요된다고 생각했는데, 최악의 경우가 몇 개 발생하여 300분이 넘게 걸렸다면 최선의 경우를 고려한 것과 같은 고민을 하게 된다.

✨ 시간 복잡도 최악의 경우를 고려한 경우

• 극단적인 예이지만, 최악의 경우가 발생하지 않기를 바라며 시간을 계산하는 것보다는 ‘최악의 경우도 고려하여 대비’하는 것이 바람직하다. 따라서 다른 표기법보다 Big-O 표기법을 많이 사용한다.
• Big-O 표기법은 ‘입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?’를 표기하는 방법이다.

Big O 정의

• 어떤 함수 f(n)의 Big-O 표기법이 O(g(n)이라는 것은, n의 값이 일정 수준이 넘어가면 그 이상의 어떤 n을 대입하여도 c*g(n)보다 결과값이 작은 상수 c가 존재한다는 뜻이다.

Big 0 함수에 대해 알아보자

O(1) : 상수형 알고리즘, 데이터 입력량과 무관하게 실행시간이 일정하다
O(n) : 선형 알고리즘, 데이터 입력량에 비례하여 실행 시간이 증가
O(logn) : 로그형 알고리즘, 데이터 입력량이 늘어날수록 단위 입력당 실행 시간이 줄어든다
O(n logn) : 선형-로그형 알고리즘, 데이터 입력량이 n배 늘면 실행 시간이 n배 조금 넘게 늘어남
O(n²) : 2차 알고리즘, 데이터 입력량의 제곱에 비례하여 실행 시간이 늘어 난다.
O(2ⁿ) : 지수형 알고리즘, 데이터 입력량이 추가될 때마다 실행 시간이 두배로 늘어난다
O(n!) : 팩토리얼형 알고리즘, 데이터 입력이 추가될 때마다 실행 시간이 n배로 늘어난다
걸리는 시간
O(1) < O(logn) < O(n) < O(n logn) < O(n²) < O(2ⁿ) < O(n!)

왼쪽에서 오른쪽으로 갈수록 느려지고 효율이 떨어 진다.

O(1)

• 일정한 복잡도(constant complexity)라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다.

• 즉, 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있다는 의미이다

• 예제 : 인덱스로 배열의 값하나를 찾는 것.

public static void main(String[] args) {
	int[] arr = {1, 2, 3, 4, 5};
	int index = 1;
	int result = O_1_algorithm(arr, index);
	System.out.println(result); // 2
}

public static int O_1_algorithm(int[] arr, int index) {
	return arr[index];
}

• 위 예제에선 입력값이 아무리 커져도 index를 이용해 바로 배열의 값을 찾아 낼 수 있다.

O(log n)

• 로그 복잡도(logarithmic complexity)라고 부르며, Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가진다.

• 예제 : 바이너리 서치 (재귀 함수로 구현)

int BinarySearchRecursive(int arr[], int target, int low, int high) {
    if (low > high) 
        return -1;

    int mid = (low + high) / 2;   //중간값 찾기
    
    if (arr[mid] == target)
        return mid;
    else if (arr[mid] > target)
        return BinarySearchRecursive(arr, target, low, mid-1);
    else
        return BinarySearchRecursive(arr, target, mid+1, high);
}

• 1~100까지 중에 임의의 한개의 숫자를 찾는 경우
• 매번 숫자가 반으로 줄어들기 때문에 최악의 경우에도 7번이면 찾을 수 있다.
• 숫자가 더 커져서 1~10000이 된다고 한다면? 최악의 경우에도 14번이면 찾을 수 있다.
• 이진 탐색에서 최악의 시나리오는 비교 log₂(n)번을 수행
• 데이터량이 늘어나도 출력에 걸리는 시간은 로그적으로 증가

O(n)

• 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.

• 예제 : 1~n까지 숫자의 총 합

public static void main(String[] args) { 
	O_n_algorithm(n);
}

public static int O_n_algorithm(n) {
	int answer = 0;
    
	for(int i =0; i<n; i++) {
    	answer +=i;
    }
    return answer;
}

public static int another_O_n_algorithm(n) {
	int answer = 0;
    
	for(int i =0; i<2n; i++) {
    	answer +=i;
    }
    return answer;
}

• O_n_algorithm 함수에선 입력값(n)이 1 증가할 때마다 코드의 실행 시간이 1초씩 증가한다.
• 즉 입력값이 증가함에 따라 같은 비율로 걸리는 시간이 늘어나고 있다. 그렇다면 함수 another_O_n_algorithm 은 어떨까?
• 입력값이 1 증가할때마다 코드의 실행 시간이 2초씩 증가한다.
• 이 알고리즘은 O(2n) 이라고 생각할 수 있다. 그러나, 사실 이 알고리즘 또한 Big-O 표기법으로는 O(n)으로 표기한다.
• 입력값이 커지면 커질수록 계수의 의미가 없기 때문에, 같은 비율로 증가하고 있다면 2배가 아닌 5배, 10배로 증가하더라도 O(n)으로 표기한다.

O(n²)

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

• 예제 : 중첩 반복문 (1~n단까지의 구구단을 나타냄)

public static void O_quadratic_algorithm(n) {
	for (int i = 1; i < n; i++) {
    	for (int j = 1; j < n; j++) {
			System.out.println(i * j);      
    	}
  	}
}

• 처음 i가 1일때 j는 n번 반복됨.
• 2,3...n일때도 j는 매번 n번 반복됨.
• n x n = n² 의 시간 복잡도를 가지기때문에 O(n²)으로 표현.

📌 참고
계수는 입력 크기가 무한대로 증가함에 따라 알고리즘의 성장률에 영향을 미치지 않기 때문에 일반적으로 Big O 표기법에서 고려되지 않습니다. 그러나 n³ 및 n⁵와 같은 서로 다른 지수는 O(n²)와 동일하지 않은 별도의 시간 복잡도를 갖습니다 .

O(2ⁿ)

• 기하급수적 복잡도(exponential complexity)라고 부르며, 매우 느린 시간 복잡도를 가집니다.
  

• 예 : 피보나치 수열의 n번째 숫자를 가져오는 함수.

public static void main(String[] args) {
	Scanner scanner = new Scanner(System.in);
    
    int n = scanner.nextInt();
    
	int result = fibonacci(n);
    
    System.out.println(result);
   
    }

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

• 재귀로 구현하는 피보나치 수열은 O(2ⁿ)의 시간 복잡도를 가진 대표적인 알고리즘이다.

공간 복잡도

• 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양.
• 시간과 공간은 반비례적 경향이 있음
• 최근 대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선
• 그래서! 알고리즘은 시간 복잡도가 중심

✨ 총 필요 저장 공간

• 고정 공간 (알고리즘과 무관한 공간): 코드 저장 공간, 단순 변수 및 상수
• 가변 공간 (알고리즘 실행과 관련있는 공간): 실행 중 동적으로 필요한 공간

✨ 공간 복잡도 표기

• 공간 복잡도 계산은 시간 복잡도 계산과 비슷하게 빅 오 표기법으로 표현한다.
• 추가 메모리 공간의 양에 대한 상한을 표기

S(P) = c + Sp(n)
c: 고정 공간
𝑆𝑝(𝑛)Sp(n): 가변 공간

📌 고정 공간은 상수이므로 공간 복잡도는 가변 공간예 좌우된다. 공간 복잡도 계산은 실제 알고리즘 실행시 사용되는 저장공간을 계산하면 됨

O(1)

• 예제 : n! 구하기(반복문)
  • 반복문을 통해서 구현하므로 result에 저장하기 때문에 공간복잡도는 O(1)이다.
  • 사용하는 변수 n, i, result

public int get_factorial(int n)	{
    int i = 0;
    int result = 1;
    
    for(i = 1; i <= n; i++)	{
        result = result * i;
    }
    return result;
}

O(n)

• 예제 : n! 구하기(재귀함수)
  • 재귀 함수를 통해서 구현하므로 변수 n에 따라서 변수 n이 n개가 만들어지게 됨
  • factorial 함수를 재귀 함수로 1까지 호출하였을경우 n부터 1까지 쌓임.

public int factorial(int n) {
    if(n == 1) {
        return n;
    }
    return n*factorial(n-1);
}