1. 지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.

• 버블정렬

  • 장점 : 구현이 간단하다.

  • 단점 : 성능이 좋지 않다.

  • 시간 복잡도 : O(n²)

• 선택정렬

  • 장점 : 구현이 간단하다.

  • 단점 : 성능이 좋지 않다.

  • 시간 복잡도 : O(n²)

• 삽입정렬

  • 장점 : 구현이 간단하다.

  • 단점 : 성능이 좋지 않다.

  • 시간 복잡도 : O(n²)

• 병합정렬

  • 장점 : 성능이 좋다.

  • 단점 : 구현이 복잡하다.

  • 시간 복잡도 : O(nlogn)

• 퀵정렬

  • 장점 : 성능이 좋다. 또한

  • 단점 : 구현이 복잡하다.

     

  • 시간 복잡도 : Θ(nlogn), O(n²) (대부분 좋은 피벗을 선택하고 최악의 경우가 발생할 경우가 극히 낮아서 병합정렬에 비해 더 적은 비교와 더 적은 메모리 공간을 차지하여 더 좋은 알고리즘으로 평가된다.)

2. 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.

• 메모이제이션을 사용하여 재귀로 쉽게 구현은 가능할 수 있지만, 결국 메모리가 부족하여 시스템에서 문제가 발생할 우려가 있으므로 구현이 조금 복잡할 수 있더라도 조금 더 메모리를 효율적으로 사용할 수 있는 타뷸레이션을 이용할 것 같다.