알고리즘 교안 107p Array vs Linked_List 시간

안녕하세요 딸기님 ㅎㅎ

똑같이 순차접근을 해야하니까 O(N)이 걸려야 하는거 아닌가요???

>>

연결 리스트에서 특정 위치에 삽입 또는 삭제를 하는 경우, 해당 위치의 바로 앞 노드를 찾아야 하므로 원칙적으로 O(N)의 시간이 걸립니다.

하지만, 삽입 또는 삭제할 노드에 이미 접근했다고 가정할 때(예를 들어, 이미 특정 노드를 가리키고 있는 포인터가 있다고 가정할 때)를 기반으로 이 작업의 시간복잡도를 계산합니다.

이 때 해당 노드의 포인터만 조정하면 되므로 O(1)의 시간이 걸립니다.

Array에서 랜덤접근이 가능하니까 접근할때는 O(1)이 걸리는거 알겠는데

삽입,삭제에 O(N)이 걸리는건 이해하기힘듭니다

>>

배열의 중간에 원소를 삽입하거나 삭제하는 경우, 해당 원소 이후의 모든 원소들을 이동시켜야 하므로, 평균적으로 O(N)의 시간이 걸립니다.

즉, 배열에서 원소를 추가하거나 제거할 때 나머지 원소들의 위치를 조정해야 하는 시간이 걸리기 때문에 O(N)입니다.

또한 해당부분에 대한 설명을 교안에다가 추가해놓았습니다. 새로 다운 받으시면 업데이트된 교안을 받으실 수 있습니다. 😀

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.