[DataStructures] 자료구조 정리

이 글은 학교 수업(이상호 교수님의 '자료구조') 을 듣고 복습차 정리한 글입니다.

 

알고리즘의 성능 분석

• 시간복잡도 T(n): 알고리즘 수행에 필요한 연산의 개수

• 빅오 표기법: 함수의 상한 f(n)<=c*g(n)

• n! > 2^n > n^2 > n > nlog2n > n > n^(½) > log2n>1

• 빅오메가표기법: 함수의 하한f(n) >= c*g(n)

• 빅세타표기법: 함수의 하한, 상한 동시에(평균 x) c1*g(n) <= f(n) <= c2*g(n)

• 최선, 평균, 최악의 경우

• 평균: 확률적인 가정이 필요

• 공간복잡도 S(n): 전체 필요한 공간의 크기

 

재귀와 반복

• 재귀: 재귀호출

• 함수 호출의 오버헤드(부가적인 연산)가 있음

• 시스템스택(지역변수,복귀주소)의변화/활성레코드

• 반복: for, while, repeat문

• 피보나치 수: f(n)=f(n-1)+f(n-2)

• 시간복잡도 T(n)=T(n-1)+T(n-2)+1 > T(n)=c^n

• 하노이 타워

• 시간복잡도 T(n)=2T(n-1)+1 > 2^n

void hanoi_tower(int n, char from, char aux, from to){

    if(n==1) printf(“원판1을 %c에서 %c로 옮긴다”, from, to);

   else

hanoi_tower(n-1, from, to, aux);

printf(“원판 %d를 %c에서  %c로 옮긴다”, from, to);

hanoi_tower(n-1, aux, from, to);

}

 

구조체: struct person{};/typedef struct person{}_person;

포인터

• &연산자: 변수의 주소

• *연산자: 포인터가 가르키는 내용

p//포인터의 값

*p//포인터가가르키는 값

(*p)++ vs *p++=*(p++):가르키는 값 가져오고 포인터 증가

p+1, p-1: 포인터p가 가르키는 객체의 바로 앞, 뒤 객체

포인터가 아무것도 가르키지 않을 때 NULL로 설정

명시적인 타입 변환 (float *)로 타입간 변환

동적 메모리 할당

• 프로그램이 시작후

• 크기 변경 가능

• malloc할당, free반납, sizeof(바이트단위)크기반환

정적 메모리할당

• 프로그램이 시작 전

• 크기 변경 불가

 

리스트ADT

• 배열: 삽입, 삭제시 오버헤드/크기제한된 항목/임의접근

• 연결리스트: 크기제한없음/순차접근

• 노드: 데이터필드 + 링크필드

• 이중연결리스트는 단순연결리스트가 선행노드 못가서 만든거

스택ADT

• 선형 큐

• 환형 큐: 하나의 공간을 항상 비워둔다.

• 포화상태 = 다 있고 하나 없는 상태

• 다 있는 상태 > 오류

• 연결 스택

 

트리ADT

• 노드/루트/부분트리/단말노드,리프/내부노드/자식/형제/부모/조상노드/고유조상노드/후손노드/레벨(각층의번호)/높이(트리의 최대레벨)/차수(노드가가지는자식노드개수)

• 이진트리: 공집합/루트+오른쪽부분트리(이진트리)+왼쪽부분트리(이진트리), 구분되어있으므로 순서화트리

• 노드가 N 개 간선 N-1개/높이 n-1~log2n

• 높이 h 노드 (h+1 ~2^(h+1)-1)

• 노드 i면 부모 [i/2] 왼쪽노드 2i오른쪽 2i+1 (완전이진트리여야 좀 영향이 있음)

• 이진탐색트리를 중순위 운행시 오름차순 정렬값

• 종류

• 포화이진트리: 꽉참

• 완전이진트리: 왼오로(위에는 다 차있)

• 경사이진트리

• 이진탐색트리:binarysearch(모든값유일)

• 삭제, 삽입 모두 탐색 실패 위치 찾기

• 시간복잡도 O(log2n~n)

• 운행

• 전순위preorder 운행 VLR <스택

• 중순위inorder 운행 LVR <스택

• 후순위postorder 운행 LRV <스택

• 레벨순위levelorder 레벨 순으로 <큐