배열과 링크드리스트에서의 빅오 [알고리즘 코딩 테스트 입문부터 합격까지 (Feat. 컴공선배 알고리즘캠프)]

배열의 경우

탐색을 할 경우:

arr[2] 는 arr[0]의 주소 + 2*(해당 타입의 바이트 수)를 의미하므로 1번의 계산으로 원하는 위치를 특정할 수 있다

이는 O(1)이 됨을 뜻한다

 

추가/삭제를 할 경우:

만약 arr[2] = 4를 넣고 싶다면

기존의 arr[2] ~ arr[6] 까지의 값들을 한칸씩 뒤로 미뤄야 한다

만약 맨 뒤에 넣고 싶다면 옮길 필요가 없으니 1번이면 되지만

맨 앞에 넣고 싶다면 모든 값을 한번씩 옮겨야하니 N이 된다

O(빅오) 에서는 최악의 상황을 가정하므로 이때는 O(N)이 됨을 뜻한다

 

링크드리스트의 경우

탐색을 할 경우:

링크드리스트에서는 99의 값의 위치를 찾으려고 해도 한번에 찾을 수 없다

99를 찾으려면 0의 위치를 찾아야 하고, 0을 찾으려면 5의 위치를 찾아야 한다 즉 N번째의 요소를 찾기 위해서는 N번의 수행이 반복되어야 한다는 뜻이다 고로 O(N)이 된다

 

추가/삭제를 할 경우:

0와 99사이에 4 라는 요소를 추가하고 싶다면 0요소의 가리키는 주소를 4번 요소로 향하게 하고 4번 요소의 가리키는 주소를 99를 향하게 하면 된다, 즉 2번의 수행이 요구되는데 O(빅오)에서는 상수 횟수는 1로 표기되기 때문에 O(1)이 된다

(O(빅오) 예시 :  n^2 +n +1 ==> O(n^2) , n+3 ==> O(n) , 5 ==> O(1) )