TIL [자료 구조 - Time Complexity]

dlrbwls0302·2021년 1월 22일
0

Complexity Analysis

알고리즘이 문제를 푸는데 시간과 공간이 얼마나 걸리는지 알 수 있는 지표이다. 시간과 공간이 얼마나 걸리는 지에 따라 그 알고리즘이 얼마나 효율적인지 분석할 수 있다. 문제가 커질 수록 우리가 문제를 푸는데 걸리는 시간도 증가한다. 이게 바로 시간 복잡도의 핵심이다.

1. Big-O Notaition

  1. 시간의 복잡도를 표현하기 위해 쓰인다.
  2. n개의 아이템을 갖고 있는 알고리즘의 가장 최악의 경우의 수를 표현한다.

상수를 뺀 뒤에 n이 O(...)의 속으로 들어간다.

2. 상황 별 Big-O Notation의 적용

왼쪽으로 갈수록 시간이 적게 들고 오른쪽으로 갈수록 시간이 많이 든다.

  1. Constant: O(1)은 문제의 크기가 커져도 문제를 푸는데 걸리는 시간이 항상 일정하다. 보통 배열에 있는 데이터를 찾거나 해시 테이블에 새로운 데이터를 넣을 때 걸리는 속도이다.

  2. Logarithmic: O(log n)은 걸리는 시간이 증가하다가 어느 순간 거의 일정한 속도로 유지가 된다. 가장 대표적인 예로 binary search가 잇다.

  3. Linear: O(n)은 문제의 수가 커질수록 시간도 비례하게 증가한다. 연결 리스트에서 원하는 값을 찾는게 대표적인 예이다. 연결 리스트의 크기가 커질수록 원하는 값을 찾는데 걸리는 시간도 증가하기 때문이다.

  4. Quadratic: O(n^2)은 문제의 수가 커질수록 시간이 기하급수적으로 증가한다.

  5. Exponential: O(c^n)은 거의 걸리는 시간이 거의 무한으로 증가한다. 피보나치 수열에서 memoization을 쓰지 않으면 이렇게 된다고 한다.


Data Structure With Time Complexity

1. 배열 (자바스크립트 배열 x)

  1. 배열 속 주소 찾기: 배열은 크기와 상관없이 원하는 주소를 바로 찾을 수 있기 때문에 이 작업을 하는데 걸리는 시간은 O(1)이다.

  2. 배열 속 데이터 바꾸기: 원하는 장소를 바로 찾아 이미 저장된 데이터를 다른 데이터로 바꾸면 되기 때문에 똑같이 O(1)이 걸린다.

  3. 배열 속 데이터 삽입하기: 데이터를 원하는 곳에 넣어주려고 하는데 만약 이미 다른 데이터가 있다고 한다면 그 데이터를 한 칸씩 옆으로 옮겨야 하고 그 옆에 데이터들도 다 한 칸씩 옮겨야 하기 때문에 O(n)이라고 할 수 있다.

  4. 배열 속 데이터 삭제하기: 원하는 데이터를 삭제하려면 빈 곳을 채워야하기 때문에 O(n)이 걸린다.

  5. 배열 속 데이터 찾기: 주소를 찾는 것과는 다르다. 내가 친구의 집 주소를 알고 있으면 그 친구를 찾을때 친구의 집 주소로 바로 가면 된다. 근데 내가 만약 친구의 집 주소를 모른다고 생각해보자. 집집마다 돌아다니면서 노크하고 'xx의 집 맞나요?'라고 물어봐야 한다. 이것도 마찬가지로 일일이 배열 속 데이터들을 확인해야 하는 번거로움이 있다. 따라서 O(n)만큼의 시간이 걸린다.

2. 연결 리스트 (Linked Lists)


  1. 연결 리스트에서 찾기: 배열에서는 몇 번째 주소인지만 알면 바로 접근할 수 있지만 연결 리스트는 알 수가 없기 때문에 처음(head)부터 순서대로 찾아야 한다. 따라서 O(n)만큼의 시간이 걸린다고 볼 수 있다.

  2. 연결 리스트 속 데이터 바꾸기: 처음(head)부터 순서대로 찾아야 하는건 똑같다. 따라서 O(n)만큼의 시간이 걸린다.

  3. 연결 리스트 속 데이터 삽입하기: 맨 마지막(tail)에 새로운 데이터를 추가한다고 생각해 보자. 새로 삽입하는 데이터를 tail로 바꿔주고 기존의 tail이였던 데이터를 연결만 하면 된다. 그러면 새로 추가된 데이터가 tail이 된다. 따라서 O(1)만큼의 시간이 걸린다.

  4. 연결 리스트 속 데이터 삭제하기: 삭제하고 싶은 데이터가 head이면 바로 삭제가 가능하다. 따라서 O(1)만큼의 시간이 걸린다. 삭제하고 싶은 데이터가 중간에 있다면 원하는 위치를 찾아야 한다. 데이터 전, 후의 데이터들을 연결해주어야 하는데 알다시피 노드는 자신의 다음 노드만 알지 전의 데이터를 모른다. 따라서 전의 노드를 찾기 위해 처음(head)부터 훑어야 하므로 걸리는 시간도 O(n)이다.

3. 이중 연결 리스트 (Doubly Linked Lists)

  1. 이중 연결 리스트 속 데이터 삭제하기: 이중 연결 리스트는 일반 연결 리스트와는 다르게 자신의 전, 후의 데이터를 알고 있다. 따라서 자신의 전, 후의 데이터를 연결해주고 삭제하고 싶은 데이터와의 연결을 끊으면 되기 때문에 O(1)이 걸린다.

4. 트리 (Trees)

  1. 트리 구조 속 데이터 찾기: 트리 구조 내에 특정 데이터를 찾아야 할 경우 최악의 경우엔 하나 하나 다 찾아봐야 할 수도 있기 때문에 걸리는 시간은 O(n)이다.

5. 이진 탐색 트리 (Binary Search Trees)

  1. 이진 탐색 트리 속 데이터 찾기: 항상 루트 노드보다 큰지, 작은지 만 확인하면 된다. 루트 노드보다 클 경우 왼쪽, 작을 경우 오른쪽으로 가고 또 다시 내려가서 부모 노드보다 큰지, 작은지 확인하면 된다. 이때는 O(log n)만큼의 시간이 걸린다고 볼 수 있다.

만약 루트 노드보다 작은 수만 추가 될 경우 연결 리스트와 같은 구조가 될 수도 있다. 이럴 경우 노드의 수만큼 탐색하면 되기 때문에 O(n) 만큼 시간이 걸린다.

profile
오늘의 공부가 쌓여서 내일의 나를 만들어낸다.

관심 있을 만한 포스트

0개의 댓글