[DataStructure] 자료구조의 큰 그림

[자료구조와 알고리즘]

자료구조

• 자료구조 : 데이터를 다루기 위한 어떠한 구조

---

알고리즘

• 알고리즘 : 어떠한 목적을 이루기 위해 필요한 일련의 연산 절차

---

⇒ 어떤 자료구조가 사용되었는지에 따라 사용 가능한 알고리즘이 달라짐

[시간 복잡도와 공간 복잡도]

시간 복잡도

• 시간 복잡도(time complexity) : 입력 크기에 따른 프로그램 실행 시간(연산 횟수)의 척도
  • 실행 시간은 연산의 횟수에 비례

---

공간 복잡도

• 공간 복잡도(space complexity) : 입력에 따른 메모리 사용량의 척도
• 메모리 사용량 多 → 공간 복잡도 大 / 메모리 사용량 少 → 공간 복잡도 小

⇒ 소스 코드나 프로그램이 얼마나 효율적인지 판단하는 척도 (대부분 시간 복잡도 사용)

---

표기법

• 빅 오 표기법(big O notation) : 함수의 점근적 상한을 표기하는 방법→ 공간 복잡도를 표현 시 입력에 따라 필요한 메모리 자원의 양에 대한 점근적 상한을 의미
  • 점근적 상한이란?
    • n이 증가해 무한대로 커진다고 가정 → 실행 시간도도 n에 따라 증가 → 실행 시간 증가에도 한계 존재 (한계 = 점근적 상한)
  • O(상한(n))
    • n이 점점 증가해 무한대로 커져도 실행 시간이 대략 이 이상(상한)은 커지지 않는 것을 의미

O(n^2) : n이 증가하더라도 실행 시간 증가율이 n^2보다 작다는 것을 의미

• • •  
    •  

O(n) : n이 증가하더라도 대략 n번 이상으로 연산하지는 않는 것을 의미

• • •  
  • 빅 오 표기법 유의점
    • 점근적 상한 표현시 최고차항의 차수만 고려
      
      
• → 시간 복잡도를 표현 시 입력에 따른 실행 시간의 점근적 상한을 의미
• 빅 세타 표기법(big θ notation) : 평균적인 실행 시간
•  

θ(n^2) : n이 증가하더라도 실행 시간 증가율은 n^2와 같다는 것을 의미

•  
• 빅 오메가 표기법(big Ω notation) : 입력에 대한 실행 시간의 점근적 하한
•  

Ω(n^2) : n이 증가하더라도 실행 시간 증가율은 n^2보다 크다는 것을 의미

•  
• 정렬 알고리즘의 시간 복잡도
  • 삽입 정렬 : O(n^2)
  • 선택 정렬 : O(n^2)
  • 버블 정렬 : O(n^2)
  • 병합 정렬 : O(n log n)
  • 퀵 정렬 : O(n log n)
  • 힙 정렬 : O(n log n)

---

💡 참고 자료

• https://www.freecodecamp.org/news/big-o-cheat-sheet-time-complexity-chart/
• https://blog.chulgil.me/algorithm/