[C언어] 자료구조 - 개념 정리

 

1. 알고리즘 시간복잡도

시간복잡도 O(1) : 알고리즘의 수행시간이 입력 데이터 수와 관계없이 일정하다

 

 

2. 알고리즘 복잡도

for(int i = 0; i < n; i *= 2 ) 　　sum++;

O(logn)

 

 

3. 용어정리

수행시간 : 순환이 반복보다 더 길다

데이터 타입 : 객체와 그 객체 위에 작동하는 연산들의 집합

알고리즘 공간복잡도 : 필요한 공간의 양

알고리즘 시간복잡도 : 필요한 컴퓨터의 시간의 양

 

 

4. 연결리스트

두 개의 리스트 하나로 합칠 때 효율적.

검색 : O(N)

삭제 : 이전노드 알 경우 O(1)

 

 

5. 원형연결리스트

헤드포인터가 마지막 노드 가리킬 경우 : 맨앞 삽입 & 맨뒤 삽입 쉬움

첫번째 노드 검색 시간 O(1)

 

 

6. 이중원형연결리스트

원형리스트 : 원형이 이전으로 순회할 수 없고, 삭제할 노드에 대한 포인터만으로 삭제할 수 없다

=> 이중원형은 가능

 

 

7. 배열

1) 순서리스트 표현위해 사용

2) 대부분 데이터 연속적으로 할당

3) k번째 원소값 검색 실행시간 O(1)

 

 

8. 이중연결리스트

특정노드의 앞뒤에 삽입,삭제 O(1)

 

 

9. 데크

오른쪽 끝 원소 삭제가 제일 오래걸림

 

 

10. 3진트리

공백링크필드 n*3-(n-1)
n은 노드개수

 

 

11. 연결리스트로 표현한 트리

부모노드 찾기 어렵다