[알고리즘]메모

기억해둘만한 사항 정리

이분탐색 시 left, right index

• while (left + 1 < right) left = mid, right = mid
• while (left <= right) left = mid + 1, right = mid - 1

시간복잡도 계산 방법

master therem

• 나누어지는 문제의 개수: a
• 분할 후 문제의 크기: b
• 각 문제마다 병합 단계에서 걸리는 시간: O()

If T(n) = aT(n/b) + O(n^d) for constants a > 0, b > 1, d>=0, then

T(n) = O(n^d)          if d > log_ba
           O(n^dlogn)  if d = log_ba
           O(n^log_ba)     if d < log_ba

ex) T(n) = 2T(n/2) + O(n) => T(n) = O(nlogn)

배열 VS 연결리스트

배열의 장점

• random access 가능해서 특정 인덱스 값을 참조하는데 O(1)
• 연결리스트는 무조건 O(k)

연결리스트의 장점

• k번째 노드 조회(삽입, 삭제 포함) 시 O(k) (k번째 노드 포인터를 알 경우 O(1))
• 배열은 무조건 O(n-k)

출처