저도 틀릴 수 있으니 맹신하지 마시고 대충 참고용으로만 읽으세욤.

1.정렬된 배열에서 저장된값찾기
2.linked 리스트에서 저장된값찾기
3.배열에서 정해진갑삽입
4.링크드~~정해진값삽입


1번은 binary search로 O(lgn).

2번은 링크드리스트는 무조건 걍 처음부터 차례대로 찾아야 되니까 O(n)

3번은 값이 들어갈 위치를 찾는데 O(lgn), 삽입하려면 그 위치 뒤에 있는 녀석들을 보두 한칸씩 밀어줘야 하니까 O(n).
 그래서 O(lgn)+O(n) = O(n)
   [사실 이렇게 표기하는게 맞는지는 모르겠넹용.]

4번은 값이 들어갈 위치를 찾는데 O(n), 삽입하는데는 O(1)
 그래서 O(n)
 만약에 이미 값이 들어갈 위치를 알고 있다면 삽입만 하면 되니 O(1)


삽입정렬은

원소 1개를 정렬하는데 1번 연산

n개를 정렬하기 위해서는 먼저 n-1개를 정렬하고 n번째 원소를 정렬된 배열 속에 삽입하면 됨.

원소 하나를 정렬된 배열에 집어넣으려면 최대 n번 연산

[이게 삽입정렬 맞는지 가물-_-;]

그래서 점화식을 세우면

InsertionSort( 1 ) = 1
InsertionSort( n ) = n + InsertionSort( n-1 )

유사코드로 한다면
InsertionSort(n) =
if n=1 then return 1
else return n+InsertionSort(n-1)
정도?


저걸로 고딩때 수열 점화식을 일반항으로 고치듯이 하면

InsertionSort(n) = 1+2+3+4+...+n = n(n+1)/2


즐공~