삽입 연산의 시간복잡도 O(n)

김오왼·2022년 2월 3일
0

자료구조

목록 보기
2/29

아무 위치에나 데이터를 더해줄 때 쓰는 insertion



정적 배열에 남는 공간있을때 시간복잡도: O(n+1) == O(n)

insertion의 최악인 경우는 0번째에 끼워넣을때 O(n)


정적 배열이 꽉 찼을 경우

수용 공간이 부족하기 떄문에 새로운 배열을 만든다
1. 새로운 데이터를 위해 새 배열을 만들때 걸리는 시간 복잡도 O(n)
2. 최악의 경우 0번째 index에 요소를 추가할 경우 뒤의 모든 요소들을 한칸씩 밀어줘야될때 걸리는 시간 복잡도 O(n)
3. 요소를 데이터에 지정해줄때 걸리는 시간복잡도 O(1)
즉 O(2n+1)
4. 결국 두번쨰 경우의 시간복잡도 또한 O(n)으로 설명됨.

결론은 특정위치가 아니라 아무 자리에 요소를 삽입하는데에는 O(n)이 걸림 (느림)



삭제 또한 첫번쨰 부터 하면 최악의 경우 O(n) 끝에를 삭제할 경우 O(1)

profile
전문 금융인을 목표로하는 김야옹야옹이

0개의 댓글