시간복잡도
Array
Look up(특정위치의 데이터 가져오기) : O(1) 배열의 저장소에는 index가 있기때문에 바로 접근할 수 있다.
Assign(특정위치에 데이터 넣기) : O(1) 배열의 저장소에는 index가 있기때문에 바로 접근할 수 있다.
Insert(특정위치에 데이터 추가) : O(n) 중간에 값을 끼워넣는 경우에는 밀리는 자료들의 index를 새로 한칸씩 조정해줘야 한다. 몇개 안될 수도 있지만 시간복잡도는 최악의 경우를 가정한다.
Remove(특정위치의 데이터 제거) : O(n) 제거된 위치를 채워줘야 하기때문에 채워지는 자료들의 index를 새로 한칸씩 조정해줘야 한다. 몇개 안될 수도 있지만 시간복잡도는 최악의 경우를 가정한다.
Find (특정 value값을 찾는다.) : O(n) 인덱스값 각각 들어가서 value값을 확인해줘야 하기 때문에 일일이 다 확인해야 한다.
Linked List
array와 비슷해보이지만 다르다.
각각 요소는 자기자신의 value값과 다음 요소에 대한 정보 2가지만 가지고 있다.
그렇기때문에 시작점인 head를 꼭 알고있어야 한다.
Look up(특정위치의 데이터 가져오기): O(n) 몇번째에있는 데이터값을 확인해야하는데 링크드 리스트는 index값이 없다. 만약 n번째 인덱스에 접근하려면 n번 이동해야 한다.
Assign(특정위치에 데이터 넣기) : O(n) 특정위치까지 이동하게되면서 최대로는 n번 이동해야 한다.
Insert(특정위치에 데이터 추가) : O(1) 배열과는 다르게 밀리는 값들이 index가 없기때문에 현재 추가하는작업만 수행된다. 2번의 수행(이전에서 이어지기, 이후로 잇기)만 필요하다.
Remove(특정위치의 데이터 제거) : O(n) 중간노드를 지울때 2가지 작업이 필요하다. 내가 가르키고있는 다음노드와의 연결끊기, 이전노드와 다음노드를 나빼고 이어주기
2가지작업이지만 2번째 작업이 어렵다. 링크드리스트는 다음노드에 대한 정보만 있기때문에 나를 가르키는 노드를 찾으려면 최대 n번의 수행이 필요하다.
Find (특정 value값을 찾는다.) : O(n) head부터 tail까지 value값이 내가 찾는값인지 확인해봐야 하기 때문에 최대 n번 수행하게 된다.
Trees
트리는 내값과 부모? 자식에 대한 정보를 가지고 있다.
Find (특정 value값을 찾는다.) : O(n) 모든자식노드들을 내려가서 확인해봐야 한다.
Binary Serach Trees
Find (특정 value값을 찾는다.) : O(log n) 바이너리 서치트리는 특수한조건(왼쪽은 작고 오른족은 크다)이 있기 때문에 검색할때 검색횟수가 현저히 줄어든다.
