🤍 알고리즘 - 시간복잡도와 공간복잡도가 높을 경우 취할 수 있는 일반 전략 3가지 정도 설명하시오.

6) 알고리즘 - 시간복잡도와 공간복잡도가 높을 경우 취할 수 있는 일반 전략 3가지 정도 설명하시오.

• 시간 복잡도

  • 시간 복잡도의 수학적 정의는 다음과 같다.

  • 이때 f(n)은 만든 알고리즘의 실제 running time을 의미한다.

  • 예시로

    

  • 다음과 같이 가정한다면

    

  • 가 성립되는 k와 n이 존재하기 때문에 내가 만든 알고리즘 f(n)은 빅-오 표기법으로

    

  • 으로 나타낼 수 있다.

• 이것을 볼 때 왜 빅-오를 n^2 으로 잡는지, 어떻게 n^2+2n+3의 상한지가 될 수 있을까 생각할 수 있다. 이유는 시간 복잡도가 점근적 표기법을 따르기 때문이다. 점근적 표기법은 n → ∞일 때의 시간 복잡도를 표현하는 방법이다.

• 시간 복잡도는 보통 최악의 경우를 따지는 빅-오 표기법으로 표현된다. 그렇다면 최선의 경우도 복잡도를 나타낼 수 있지 않나? 라는 의문이 들었다.

  • 예를 들어, 5 4 7 10 1 2 라는 숫자 배열이 있을 때, 5라는 숫자를 순차 탐색한다고 가정하면 첫 번째 탐색에서 바로 5를 찾게 된다. 이게 바로 최선의 경우이다.

  • n^2 알고리즘처럼 복잡한 알고리즘도 최선의 경우에는 특정 값을 한 번에 찾을 수 있어 복잡도가 O(1)일 수 있다. 하지만 최선의 경우는 모든 알고리즘에 대해서 성능 차이가 크게 나지 않기 때문에 일반적으로 비교가 어렵다. 그래서 보편적으로 최악의 경우를 기준으로 시간 복잡도를 비교하는 것이다.

---

시간복잡도가 높은 경우 취할 수 있는 일반 전략

• 코드 최적화 : 불필요한 연산을 제거하거나 효율적인 알고리즘을 선택하는 것이 중요하다. O(n^2) 알고리즘 대신 O(n log n) 알고리즘을 사용하는 것이 큰 차이를 만들 수 있다. 이를 통해 처리 시간을 줄이고 성능을 향상시킬 수 있다.

• 메모제이션 : 이전에 계산한 결과를 저장해 불필요한 계산을 줄인다. 이로써 동일한 연산을 반복하지 않게 되어 시간 복잡도를 줄일 수 있다. 특히 재귀적인 알고리즘에서 많이 사용된다.

• 병렬 처리 : 여러 처리 유닛을 활용하여 작업을 동시에 수행한다. 병렬화 가능한 작업이라면, 여러 코어나 쓰레드를 활용해 한꺼번에 처리할 수 있기 때문에 작업 속도를 크게 개선할 수 있다.

---

공간복잡도가 높은 경우 취할 수 있는 일반 전략

• 고정 공간보다 가변 공간을 사용할 수 있는 자료구조를 사용한다. 필요에 따라 공간을 동적으로 할당하는 자료구조, 예를 들어 연결 리스트나 동적 배열을 사용하면 고정된 크기의 배열보다 메모리를 효율적으로 사용할 수 있다.

• 함수 호출 시 생성되는 지역 변수나 동적으로 할당되는 객체는 모두 메모리를 차지하므로, 이런 자원 사용을 최소화하는 것이 좋다. 가능하면 한 번에 필요한 만큼만 메모리를 사용하도록 설계한다.

• 재귀 함수는 호출될 때마다 스택 메모리를 사용하기 때문에 동일한 로직을 반복문으로 구현할 수 있는 경우라면 반복문을 사용하는 것이 더 효율적이다. 특히 깊은 재귀는 메모리 누수를 유발할 수 있으므로 주의해야 한다.