algorithm | array 기본

> Array와 algorithm

▶︎ stable, unstable

Array와 관련된 문제는 대부분 sorting(heap, quick, merge)과 관련이 있습니다.

time complexity는 O(nlogn)을 가집니다.

stable한 algorithm에는 merge가, unstable한 algorithm에는 quick과 heap이 있습니다.

stalble sort의 경우 다음과 같이 이름 또한 일관성 있게 정렬됩니다.

unstalble sort는 이름에 대한 정렬은 일관성이 없습니다.

▶︎ search, binary search

search의 time complexity는 배열의 element를 순회해야 하므로 O(n)을 가집니다.

만약 배열이 정렬이 되어있는 경우라면 binary search를 사용할 수 있고 time complexity는 O(logn)을 가집니다.

이 두가지가 array의 기본 operation이고 graph와 같은 2차원, 다차원 배열 문제가 나오기도 합니다.