시간복잡도와 공간복잡도

시간 복잡도와 공간 복잡도는 알고리즘의 효율성을 측정하는 두 가지 주요 지표입니다.

시간 복잡도는 알고리즘이 문제를 해결하는 데 필요한 시간을 나타냅니다. 입력 크기에 따라 얼마나 많은 계산이 필요한지를 설명합니다. 예를 들어, 'O(n)'의 시간 복잡도를 가진 알고리즘이 있다면, 입력 데이터의 크기 n에 비례하여 시간이 증가한다는 것을 의미합니다.

공간 복잡도는 알고리즘이 문제를 해결하는 데 필요한 메모리 공간을 나타냅니다. 입력 크기에 따라 얼마나 많은 저장 공간이 필요한지를 설명합니다. 예를 들어, 'O(n)'의 공간 복잡도를 가진 알고리즘이 있다면, 입력 데이터의 크기 n에 비례하여 메모리 사용량이 증가한다는 것을 의미합니다.

개발자는 시간 복잡도와 공간 복잡도를 모두 고려하여 알고리즘을 선택하고 구현해야 합니다. 일반적으로 두 가지 복잡도 사이에는 트레이드오프(trade-off) 관계가 있습니다.

즉, 시간 복잡도를 줄이려면 더 많은 메모리를 사용해야 할 수 있고, 반대로 메모리 사용량을 줄이려면 더 많은 계산이 필요할 수 있습니다. 

어떠한 알고리즘의 성능 평가가 필요할 때 복잡도의 척도를 사용하는데 그 복잡도가 낮을수록 좋은 알고리즘입니다. 시간 복잡도는 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미하고 공간 복잡도는 특정 알고리즘이 어떤 문제를 해결하는데 차지하는 공간(메모리)을 의미합니다.

 

시간 복잡도란 특정 크기의 입력을 기준으로 할 때 필요한 연산의 횟수를 나타냅니다. 시간 복잡도에는 빅오 표기법이라는 복잡도를 나타내는 점근 표기법 중 가장 많이 사용되는 표기법을 사용합니다. 공간 복잡도는 프로그램 실행과 완료에 얼마나 많은 공간(메모리)가 필요한지를 나타냅니다. 알고리즘을 실행시키기 위해 필요한 공간은 고정 공간과 가변 공간이 있습니다.

 

시간복잡도(time complexity)란 알고리즘을 실행하여 종료할때까지 필요한 시간 입니다. 공간복잡도(space complexity)란 알고리즘을 실행하여 종료할때까지 필요한 기억창치의 크기 입니다. 시간복잡도는 알고리즘을 구성하는 명령어들이 몇 번이나 실행이 되는지를 센 결과에 각 명령어의 실행시간을 곱한 합계를 의미합니다. 그러나 각 명령어의 실행 시간은 특정 하드웨어 혹은 프로그래밍 언어에 따라서 그 값이 달라질 수 있기 때문에 알고리즘의 일반적인 시간 복잡도는 명령어의 실제 실행시간을 제외한 명령어의 실행 횟수만을 고려하게 됩니다. 공간 복잡도는 알고리즘과 무관한 부분과 밀접한 부분으로 분류 할 수 있는데, 일반적으로 공간 복잡도를 분석할때는 알고리즘과 밀접한 부분 , 알고리즘의 특성과 밀접한 관계가 있는 부분으로써 문제를 해결하기 위해 필요로 하는 공간, 즉, 변수를 저장하기 위한 공간이나 순환 프로그램일 경우 순환스택을 계산하여 공간 복잡도를 계산합니다.

"순환스택"이라는 용어는 일반적으로 많이 사용되지 않는 표현입니다. 가장 근접하게 연결될 수 있는 개념은 "순환 버퍼(Circular Buffer)" 또는 "환형 큐(Circular Queue)" 일 것 같습니다. 이는 배열을 기반으로 한 데이터 구조로, 시작과 끝이 연결되어 "원형"처럼 동작하는 특징을 가집니다.

순환 버퍼는 고정된 길이를 가지고, 데이터가 들어오면 시작점부터 차례로 저장합니다. 버퍼가 꽉 차면, 다음 데이터는 배열의 시작점부터 다시 저장됩니다. 이렇게 하면 오래된 데이터는 새로운 데이터로 덮어쓰게 됩니다.

이는 특히 스택과 같은 자료 구조에서는 일반적으로 사용되지 않으며, 큐에서 더 자주 보입니다. 스택은 LIFO(Last In First Out) 원칙에 따라 동작하기 때문에, 순환적인 동작이 일반적이지 않습니다. 반면에, 큐는 FIFO(First In First Out) 원칙에 따라 동작하므로, 순환 버퍼 구조를 사용하여 효율적으로 구현할 수 있습니다.

최근에는 대용량 시스템이 보편화되면서 공간복잡도보다는 시간복잡도가 중심이 되고 있습니다.

 

** 빅 오 표기법(Big O notation)은 알고리즘의 복잡도를 표현하는 방법입니다. 이는 알고리즘이 처리해야 하는 데이터의 크기에 따라 시간 복잡도와 공간 복잡도가 어떻게 증가하는지를 설명하는 표기법입니다.

빅 오 표기법은 알고리즘의 최악의 성능을 표현합니다. 즉, 입력 크기가 무한대로 가정했을 때, 알고리즘이 어떻게 수행될지에 대한 상한선을 설명합니다.

다음은 몇 가지 일반적인 빅 오 표기법의 예입니다:

• O(1): 상수 시간 복잡도. 입력 데이터의 크기와 관계없이 알고리즘의 실행 시간이 일정합니다. 예를 들어, 배열의 특정 인덱스에 있는 요소에 접근하는 작업은 O(1)의 시간 복잡도를 가집니다.
• O(n): 선형 시간 복잡도. 입력 데이터의 크기와 알고리즘의 실행 시간이 직접적으로 비례합니다. 예를 들어, 배열의 모든 요소를 한 번씩 방문하는 작업은 O(n)의 시간 복잡도를 가집니다.
• O(log n): 로그 시간 복잡도. 입력 데이터가 증가함에 따라 알고리즘의 실행 시간은 로그 증가합니다. 예를 들어, 이진 검색 알고리즘은 O(log n)의 시간 복잡도를 가집니다.
• O(n^2): 제곱 시간 복잡도. 입력 데이터의 크기의 제곱에 비례하여 알고리즘의 실행 시간이 증가합니다. 예를 들어, 버블 정렬 같은 간단한 정렬 알고리즘은 O(n^2)의 시간 복잡도를 가집니다.

이와 같이 빅 오 표기법은 알고리즘의 성능을 분석하고 다른 알고리즘과 비교하는 데 중요한 도구입니다.

 

**알고리즘의 공간 복잡도를 분석할 때, 고정 공간(fixed space)와 가변 공간(variable space)라는 두 가지 요소를 고려합니다.

1. 고정 공간(Fixed Space): 이는 알고리즘이 실행되는 동안 변경되지 않는 메모리 공간을 의미합니다. 고정 공간에는 알고리즘에서 사용하는 변수, 상수, 고정 배열 등이 포함됩니다. 입력의 크기에 관계없이 이 공간의 크기는 변하지 않습니다.
2. 가변 공간(Variable Space): 이는 알고리즘 실행 동안 변경될 수 있는 메모리 공간을 의미합니다. 이 공간은 입력의 크기나 알고리즘의 특정 조건에 따라 달라질 수 있습니다. 가변 공간에는 동적으로 할당되는 데이터 구조(예: 연결 리스트, 스택, 큐, 동적 배열 등), 재귀 스택 프레임 등이 포함될 수 있습니다.

알고리즘의 전체 공간 복잡도는 이 두 가지 공간의 합으로 계산되며, 일반적으로 가변 공간이 고정 공간보다 더 큰 영향을 미칩니다. 따라서 공간 복잡도 분석 시 주로 가변 공간에 초점을 맞춥니다.

1. 동적으로 할당되는 데이터 구조: 이는 프로그램 실행 중에 데이터의 크기가 변할 때 사용하는 데이터 구조입니다. 예를 들어, 리스트, 스택, 큐, 동적 배열 등이 이에 해당합니다. 이들은 데이터의 개수나 크기에 따라 메모리 공간을 늘리거나 줄일 수 있습니다.
2. 재귀 스택 프레임: 재귀 함수는 함수가 자기 자신을 호출하는 방식으로 작동하는데, 이때 각 함수 호출마다 메모리 스택에 프레임이 생성됩니다. 이 프레임은 함수의 변수, 매개변수 등을 저장하는데 사용되는데, 함수 호출이 끝나면 이 프레임은 사라집니다. 따라서 재귀 함수의 깊이(즉, 함수가 자기 자신을 몇 번 호출하는지)에 따라 필요한 메모리 공간이 달라집니다.

 

시간 복잡도 예시:

데이터 배열에서 특정 요소를 찾는 문제를 가정

1. 선형 검색(Linear Search): 이 방법은 각 요소를 하나씩 차례로 확인하여 원하는 값을 찾습니다. 최악의 경우, 배열의 모든 요소를 확인해야 하므로 시간 복잡도는 O(n)입니다.
2. 이진 검색(Binary Search): 이 방법은 배열이 정렬되어 있을 때 사용할 수 있습니다. 중간 값과 찾고자 하는 값을 비교하여 검색 범위를 절반씩 줄여나갑니다. 이렇게 로그 시간에 원하는 값을 찾을 수 있으므로 시간 복잡도는 O(log n)입니다.

이 두 가지 방법을 비교하면, 이진 검색이 선형 검색보다 더 빠르지만, 이진 검색을 사용하려면 배열이 먼저 정렬되어 있어야 한다는 제약이 있습니다.

 

공간 복잡도 예시: 재귀를 사용하는 알고리즘과 그렇지 않은 알고리즘의 비교

• 반복문을 사용한 팩토리얼 계산: 이 경우, 단지 몇 개의 변수만 필요하므로 공간 복잡도는 O(1)입니다.

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

• 재귀를 사용한 팩토리얼 계산: 이 경우, 재귀 호출이 발생할 때마다 스택에 새로운 레이어가 추가됩니다. 따라서 n이 증가함에 따라 메모리 사용량도 증가하므로 공간 복잡도는 O(n)입니다.

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

이 두 가지 방법을 비교하면, 반복문을 사용하는 방법이 재귀를 사용하는 방법보다 메모리 사용량이 적지만, 재귀를 사용하는 방법이 코드를 더 간결하고 이해하기 쉽게 만들 수 있습니다. 

1. 포트폴리오에서 시간복잡도를 낮춘 사례가 있다면 설명해주실 수 있을까요?

1. 인덱싱: 데이터베이스에서 데이터 조회 속도를 높이기 위한 주요 방법 중 하나는 인덱싱입니다. 인덱스는 테이블의 데이터를 빠르게 탐색할 수 있도록 도와줍니다. 적절한 인덱스를 설정함으로써, DBMS는 전체 테이블을 스캔하지 않고도 필요한 데이터를 빠르게 찾을 수 있습니다.
2. 필요한 데이터만 조회: 전체 엔티티를 조회하는 대신 필요한 필드만 선택하여 조회하면, 데이터 전송량을 줄이고 처리 시간을 단축할 수 있습니다. 이는 특히 대용량 데이터를 다룰 때 유용합니다.
3. 카운트 쿼리 사용: 페이지네이션을 구현할 때, 전체 데이터의 수를 알아야 할 필요가 종종 있습니다. 이럴 때 별도의 카운트 쿼리를 사용하면, 전체 데이터를 불러온 후 개수를 세는 비효율적인 작업을 피할 수 있습니다.
4. 레디스(Redis)는 인메모리 데이터베이스로, 데이터를 메모리에 저장하기 때문에 디스크 기반의 데이터베이스보다 훨씬 빠른 처리 속도를 보여줍니다. 이런 특성 때문에 레디스는 주로 캐싱, 세션 관리, 토큰 저장 등에 사용되며, 이러한 작업들은 대개 시간 복잡도가 O(1)입니다. 여기서 O(1)이란 알고리즘의 시간 복잡도 표기법으로, 입력 데이터의 크기와 상관 없이 알고리즘의 실행 시간이 일정하다는 것을 의미합니다. 즉, 레디스에서 키-값 쌍을 사용하여 데이터를 조회하거나 저장하는데 필요한 시간은 데이터의 양에 관계없이 거의 일정합니다.
5. 데이터베이스에서 인덱스를 사용하면 특정 데이터를 찾는 속도를 크게 향상시킬 수 있습니다. 예를 들어, LIKE '%word%'와 같은 검색 쿼리는 데이터베이스에서 전체 행을 스캔하므로 시간 복잡도가 O(n)이 됩니다. 하지만 B-Tree 인덱스를 사용하면 데이터를 로그 시간에 찾을 수 있게 되어 시간 복잡도가 O(log n)으로 줄어듭니다.
6. 또한, 불필요한 코드를 제거하고, 중첩된 반복문을 최적화하고, 더 효율적인 알고리즘을 사용하여 시간 복잡도를 줄이는 것은 모든 프로그래밍 작업에서 중요합니다.