Topic

data structure
algorithm

What I Learned

자료 구조(Data structure)

개념

• 컴퓨터 과학에서 효율적인 접근 및 수정을 가능하게 하는 자료의 조직, 관리, 저장을 의미
• 데이터 값의 모임, 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미

유형

선형 / 비선형 자료 구조

• 선형 구조: 데이터 원소들이 순차적으로 나열되어 있으며, 한 요소 다음에 반드시 하나의 요소만 존재하
  는 구조로 주로 배열, 스택, 큐, 연결 리스트 등 단일 경로로 탐색되는 자료구조에 해당
• 비선형 구조: 하나의 요소가 둘 이상의 요소와 연결될 수 있는 계층적 또는 네트워크 형태의 구조로
  트리나 그래프처럼 여러 방향으로 탐색되며 복잡한 관계를 표현하는 데 적합

알고리즘(Algorithm)

개념

• 어떠한 문제를 해결하기 위해 정해진 일련의 절차

성능 분석 방법

시간 복잡도(Time complexity)

• 계산 문제를 해결하는데 걸리는 시간
• CPU 자원과 밀접한 관계로 계산 양이 많으면 효율이 떨어짐
• 중심이 되는 특정 연산의 횟수를 세어 평가
• 현대에서는 시간 복잡도가 공간 복잡도보다 중요
• 공간 복잡도와 시간 복잡도는 반비례 관계일 때가 많음

공간 복잡도(Space complexity)

• 계산 문제를 해결하는데 필요한 메모리의 자원
• 메모리와 밀접한 관계로 메모리의 효율이 중요
• 중심이 되는 연산에 필요한 메모리를 측정
• 현대에서는 메모리 자원이 많아 불필요하다 느껴질 수 있지만 대량 트래픽을 처리하는 프로그램에선 메모리 자원은 절대적으로 부족

빅오(Big-O) 표기법

• Big-O 표기법은 알고리즘의 시간 및 공간 복잡도를 입력 크기 기준으로 나타내는 점근적 표기법이다.
• 최악의 경우를 기준으로 알고리즘의 성능을 비교하며 실행 시간의 증가율을 설명한다.

정렬 방법 별 시간/공간 복잡도

Java의 sort algorithm

타입	내부 알고리즘	시간 복잡도	공간 복잡도	안정성
Primitive 배열	Dual-Pivot QuickSort	O(n log n)	O(log n)	X
객체배열/List	TimSort	O(n log n)	O(n)	O

안정성:

• “O”는 stable sort(동일값 원소 순서가 보존됨)
• “X”는 unstable sort