[자료구조] 열혈 자료구조⛑️ #1

📖 윤성우. <윤성우의 열혈 자료구조>, 오렌지미디어.

---

🩵 자료구조

: 데이터의 표현 및 저장방법. 알고리즘과 밀접한 관계를 가지고 있다.

• 선형(linear) 구조 : 리스트, 스택, 큐
• 비선형 구조 : 트리, 그래프
• 파일 구조 : 순차파일, 색인파일, 직접파일
• 단순 구조 : 정수, 실수, 문자, 문자열

 

🅰 추상 자료형(ADT, Abstract data type)

: 구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지 나열한 것

 

 

🆃 자료구조 & 알고리즘 평가 방법

1. 공간 복잡도(Space Complexity) : 메모리 사용량
2. 시간 복잡도(Time Complexity) : 속도
   시간 복잡도 함수 : T(n) = n^2 + n + 1 or n^2 + 2n + 1

 

🅾 빅-오(Big-Oh)

: 가장 영향력이 큰 부분
시간 복잡도 함수의 빅-오 : O(n^2)

대표적인 빅-오(성능순)

• O(1) : 상수형. 데이터 수에 상관없이 연산횟수가 고정된 유형의 알고리즘
• O(log n) : 로그형. 데이터 수의 증가율에 비해 연산횟수의 증가율이 훨씬 낮은 알고리즘
• O(n) : 선형. 데이터 수와 연산횟수가 비례하는 알고리즘
• O(n log n) : 선형로그형. 데이터의 수가 두 배로 늘 때, 연산횟수는 두 배를 조금 넘게 증가하는 알고리즘
• O(n^2) : 데이터 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘
• O(n^3) : 데이터 수의 세 제곱에 해당하는 연산횟수를 요구하는 알고리즘

---