[자료구조] 자료구조 기초

자료(Data)와 자료 구조(Data Structure)

  - 자료(데이터)를 어디에 어떻게 저장하여 관리할지 (검색, 순회, 저장, 삭제, 변경 등)

  - 자료를 담는 추상적인 툴

  - 컴퓨터의 자원은 한정적이며 제한된 제약조건 내에 정확한 결과를 내야함

  - 데이터의 형태와 쓰임에 가장 적합한 자료구조를 쓰는 것은 매우 중요

 

공간 복잡도

  - 데이터 관리에 필요한 공간

  - 데이터 양의 변화에 따른 공간의 변화

  - 예상 소요 공간 측정

 

시간 복잡도

  - 데이터 처리에 소요되는 시간

  - 데이터 양의 변화에 따른 소요 시간의 변화

  - 예상 처리 시간을 측정

  - 지연 장애가 발생했을 때 왜 발생했는지를 찾을 수 있는 근거

 

시간 복잡도

  - O(1) : 입력 데이터의 크기와 상관없이 항상 일정한 시간이 걸리는 알고리즘 ex) 배열의 Random Access, Hash

  - O(N) : 입력 데이터의 크기에 비례해서 시간이 소요되는 알고리즘

for (int i = 0; i < N; i++) {
	// do something ...
}

 

  - O(N2) : 입력 데이터의 제곱에 비례해서 시간이 소요되는 알고리즘

for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
    	   // do something ...
    }
}

 

  - O(logN) : 이진탐색(Binary search)

  - O(NlogN) : Merge sort