반응형 CS/Data Structure4 시간복잡도 big-O 시간복잡도 자료구조에 대해서 조회, 삽입, 변경(수정), 제거를 수행할 때 걸리는 시간과 입력의 함수 관계를 나타낸다. big-O 최악의 경우를 기준으로 시간 복잡도를 나타냄. 크기 비교(내림차순) O(n!) > O(2^n) > O(n^2) > O(nlog n) > O(n) > O(log n) > O(1) O(log n) < O(n) 항상 성립한다? '항상'은 아니다....단순히 값의 크기만 비교하는게 아니라 증가량의 차이도 고려하는 것 같다. (내용추가) big-Omega = 최선의 경우를 다루는 표기법 (하한점근선?) big-Theta = 최악, 최선의 중간경우를 다루는 표기법 종류는 이정도만 알고 넘어가자 자료구조별 시간복잡도 배열 Insert - O(n) 0번 인덱스에 삽입시 나머지.. 2020. 10. 28. Graph Tree BST Graph 그래프는 노드(Node, 정점 -vertex-)와 노드와 노드를 연결하는 간선(edge)로 구성된다. 간선은 방향가질수도, 무방향(undirected)일 수 있다. 진입 차수 진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름) 진출 차수(out-degree): 방향 그래프에서 외부로 향하는 간선의 수 (외차수 라고도 부름) 방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합 = 방향 그래프의 간선의 수(내차수 + 외차수) 인접 행렬 방식 NxN 불린 행렬(Boolean Matrix)로써 matrix[i][j]가 true라면 i -> j로의 간선이 있다는 뜻이다. V개의 노드를 표현하기 위해 V*V 만큼의 크기가 필요하므로 공간복잡도는 O(V^.. 2020. 10. 27. Linked List, Hash Table Linked List 단일 연결 리스트는 노드가 바로 다음 노드 방향으로 단일 연결만을 갖는 구조이다. 때문에 탐색 방향이 한쪽으로 밖에 진행되지 않는다. 이중 연결 리스트는 노드가 앞뒤의 노드와 연결된 구조이다. 양쪽으로 탐색이 가능하기 때문에 탐색의 시작을 처음과 끝 둘 중에 하나로 지정할 수 있다. 연결리스트의 임의의 위치에 노드를 추가하거나 삭제할 때 O(1)의 상수시간만큼의 시간 복잡도를 갖는다. 배열은 추가와 삭제에 대해 O(N)의 선형시간 만큼의 복잡도를 갖는다 연결리스트는 인덱스를 갖지 않는다. 그렇기 때문에 특정 데이터를 리스트에서 조회하고자 할 경우, 처음부터 전체를 확인해야 하며 O(N)의 시간복잡도를 갖는다. 조회삽입삭제Linked ListO(N)O(1)O(1) Hash Table .. 2020. 10. 26. Queue 큐 / Stack 스택 Queue 큐 큐는 일상생활에서 줄서기를 할 때와 동일한 형태로 동작하는 자료구조다. 먼저 줄을 서있던 사람이 먼저 줄에서 이탈한다. 큐도 마찬가지로 먼저 입력된 데이터가 먼저 제거된다. 시간복잡도 자료구조 조회 삽입 삭제 Queue O(n) O(1) O(1) Stack 스택 스택은 쌓여있는 접시를 사용할 때와 같은 구조다. 추가와 삭제는 스택의 최 상위에서만 수행할 수 있다. 가장 먼저 입력된 데이터가 가장 먼저 이탈한다. 시간복잡도 자료구조 조회 삽입 삭제 Stack O(n) O(1) O(1) 2020. 10. 26. 이전 1 다음 반응형
