🤍 알고리즘 - 시간복잡도와 공간복잡도가 무엇인지 설명하시오.

5) 알고리즘 - 시간복잡도와 공간복잡도가 무엇인지 설명하시오.

• 복잡도는 알고리즘의 성능을 나타내는 척도이다.

• 시간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미

  • 같은 결과를 가져오는 코드라면 시간 복잡도가 작을 수록 더 효율적인 알고리즘이다. 시간 복잡도는 여러가지 개념이 있지만 그 중 ‘worst case‘를 기준으로 표기하는 빅-오(Big-O) 표기법을 사용한다. 즉, 아무리 오래걸려도 이것보단 오래걸리지 않는 시간을 기준으로 알고리즘의 성능을 표기하는 것이다.

  • 시간 복잡도 표시

    • O(1) - 상수 시간 : 입력 크기 (n)에 상관 없이 일정한 연산을 수행하는 시간 복잡도

    • O(log₂ n) - 로그 시간 : 입력 크기 (n)이 커지면 연산 횟수가 log₂ n에 비례해서 증가하는 시간 복잡도

    • O(n) - 선형시간 : 입력 크기 (n)이 커지면 연산 횟수가 n에 비례해서 증가하는 시간 복잡도

    • O(n²) - 2차 시간 : 입력 크기 (n)이 커지면 연산 횟수가 n²에 비례해서 증가하는 시간 복잡도

    • O(2ⁿ) - 지수 시간 : 입력 크기 (n)가 커지면 연산 횟수가 2ⁿ에 비례해서 증가하는 시간 복잡도

  • 시간 복잡도를 줄이는 방법

    • 반복문의 숫자를 줄인다.

    • 적절한 자료구조를 사용한다.

    • 적절한 알고리즘을 이용한다.

• 공간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미

  • 공간 복잡도를 줄이는 방법

    • 재귀함수를 자제하거나 고정 공간보다는 가변 공간을 사용하면 공간 복잡도를 최소화 할 수 있다.

• 시간 복잡도와 공간 복잡도의 관계

  • 시간 복잡도와 공간 복잡도는 반비례하는 경향이 있다. 시간을 절약하기 위해 더 많은 공간을 사용하거나, 반대로 공간을 절약하기 위해 더 많은 시간을 소비하는 경우가 많다.

  • 또한, 최근에는 메모리 비용이 상대적으로 저렴해져 시간 복잡도에 비해 공간 복잡도의 중요성이 다소 낮아졌다. 그러나 대용량 데이터를 다루는 빅데이터 분야나 제한된 자원을 가진 임베디드 시스템에서는 여전히 공간 복잡도가 중요한 고려사항이다.

---

🧾 예상 질문

• Q. 대용량 데이터를 처리해야 할 때 어떤 자료구조를 선택할 것인가? 이유는?

  • 해시 테이블을 선택할 것이다. O(1)의 평균 검색/삽입/삭제 시간 복잡도로 대용량 데이터를 효율적으로 처리할 수 있기 때문이다. 다만 최악의 경우 충돌로 인해 O(n)이 될 수 있다는 점을 고려해야 한다.

• Q. 실시간으로 데이터를 정렬해야 하는 상황에서 어떤 정렬 알고리즘을 사용할 것인가?

  • 힙 정렬을 사용할 것. O(nlogn)의 일관된 성능을 보이며, 실시간으로 들어오는 데이터를 정렬된 상태로 유지하기에 적합하다. 또한 우선순위 큐 형태로 사용할 수 있어 효율적이다.

• Q. 데이터베이스 인덱싱에 사용되는 자료구조는 무엇이며, 왜 그 구조가 효율적인가?

  • B-Tree나 B+Tree가 주로 사용된다. O(log n)의 검색/삽입/삭제 성능을 제공하며, 디스크 기반 시스템에 최적화되어 있어 효율적이다. 특히 B+Tree는 리프 노드 간 연결로 순차 접근이 용이하다.

• Q. 캐시 시스템 구현에 적합한 자료구조는 무엇이며, 그 이유는?

  • 해시 테이블이 적합하다. O(1)로 데이터를 빠르게 검색할 수 있기 때문에 캐시 시스템의 빠른 응답 요구 사항을 충족시킨다. 추가로, LRU 캐시 같은 경우 해시 테이블과 이중 연결 리스트를 함께 사용하면 효율적이다.

• Q. 네트워크 패킷 처리나 작업 스케줄링에 자주 사용되는 자료구조는 무엇인가?

  • 우선순위 큐가 많이 사용된다. 주로 힙으로 구현되며, O(log n)의 삽입과 삭제 시간 복잡도로 우선순위 기반의 패킷 처리나 작업 스케줄링에 적합하다.