Data Structure Time Complexity
들어가기 전에 복잡도에 대해서는 Pre 과정에서 호용님이 강의하신 게 더 이해가 잘된다.
누군지는 모르겠지만 IM과정에 설명해주는 분의 강의는 봐도 잘 이해가 안 된다.
Complexity Analysis
Complexity Analysis In The Real World
How does problem size affect the time and space required by particular algorithm?
Complexity Analysis?
복잡도 분석이라고 할 수 있다.
그 중에서 시간복잡도란?
알고리즘이 그것을 푸는 데 있어서 시간과 공간을 도대체 얼마나 차지하는지를 나타내는 지표라고 보면 된다.
Why is this important?
Complexity helps us understand, and therefore improve, the efficiency of our code.
그렇다면 시간이랑 공간의 복잡도가 왜 중요한가?
그 알고리즘이 얼마나 효율적인지 나타낼 수 있게 하기 때문이다.
극단적인 예로 시간과 공간이 무한정으로 있다면, 알파고가 만들기 쉬 올 수도 있다. 그 이유는 무한정한 공간에다가 알파고의 모든 경우의 수를 계산하고 무한정의 시간 동안 계산한다면 많은 경우의 수를 훑은 다음에 최적의 경우의 수를 알 수 있기 때문에 가능할 것이다.
하지만 그것을 만드는 데 저장공간이 많이 필요할 것이다.
Why is this "really" important?
They are being asked on programming interviews!
왜 정말 중요하냐면, 프로그래밍 인터뷰에 붙기 때문이다. 알고리즘을 짤 때 돌아가는 것이 중요하고 그다음은 얼마나 효율적인 시간과 복잡도로 풀었는지가 중요하다. 그런데 이번 시간에는 공간 복잡도는 생각하지만 시간 복잡도만을 생각하도록 해보겠습니다. 숫자의 배열이 주어졌는데 그 배열에서 그 두 수의 차가 가장 큰 것을 찾을 것이다. 정리하면 숫자가 주어진 배열에서 가장 큰 두 수의 차를 구하는 것이다. 어떤 방식으로 풀 수 있는가? 이런 문제를 푸는 것을 알고리즘이라고 하며, 문제가 커질수록 시스템의 걸리는 시간이 얼마나 빠르게 혹은 늦게 비슷하게 커지는지가 시간 복잡도의 핵심이다.
모든 수의 차를 구하는 것은 다음표로 해보았다.
One Approach : Compare all numbers to all other numbers.
| 2 | 5 | 6 | ...... | 16 | |
| 2 | n/a | 3 | 4 | ....... | 14 |
| 5 | 3 | n/a | 1 | ...... | 11 |
| 6 | 4 | 1 | n/a | ...... | 10 |
| ..... | ...... | ...... | ..... | ..... | ....... |
| 16 | 14 | 11 | 10 | ...... | n/a |
How many operations do we have to do?
input size가 n이라고 한다면 for n items [ n*n = n의 제곱 ] operations
배열 안에 5개의 아이템이 있다면 25번 6개라면 36번.. 등이 된다는 것이다.
이것이 문제가 커질수록 연산이 얼마나 커지는지 감이 올 것이다.
이게 바로 시간 복잡도의 핵심이다.
다른 방법으로 풀어본다면 다음과 같다. 그 배열 안에서 가장 큰 수와 가장 작은 수를 찾는 것이다.
가장 작은 수를 먼저 찾는 것을 한다. 가장 작은 수를 찾으면 다음과 같으며 가장 큰 수를 찾으라고 하면 다음과 같다.
Approach: Find largest & smallest numbers
| 2 | 5 | 6 | ....... | 16 | |
| Is smallest? | Y | N | N | N | N |
| Is largest? | Y | Y | Y | Y | Y |
2*n = 2n이 되며, 이렇게 보면 시간 복잡도가 앞에 것보다 좋아졌다는 것을 알 수 있다.
Anoter approach
What if we knew that this was a sorted list?
Approach: Compare first & last
for a sorted list, the largest differences can be found by comparing the first and last elements
그렇다면 우리가 이미 list가 정렬되어있다고 가정을 한 경우(뒤에 있는 것은 가장 큰 숫자와 앞에 있는 것은 가장 작은 숫자)
마지막에 있는 숫자와 앞에 있는 숫자를 빼는 경우라고 나오는 값을 빼 주면 된다. 그러면 끝난다.
그러면 1번만 연산이 된다라는 것을 알 수 있다. 가장 큰 차를 발견해낼 수 있다.
가장 큰 차의 값이 되겠구나!라는 것을 알 수 있다.
가장 큰 값을 빼네 오고 두 번째 값을 빼네 오고 첫 번째와 두 번째를 빼내 온 것을 해서 3번이라고 한다. 앞에서처럼 하면 한 번이겠죠
How many operation do we have to do?
여기서는 3번의 경우가 될 것이다. -> for n items 3 operations
끝 숫자와 맨 앞 숫자와 그것을 뺀 것을 해서 3번이라고 본 것 같다.
그렇다면 5개가 있어도 3번 10개가 있어도 3번 이 되는 경우가 될 것이다.
5개에서 10개가 늘어도 연산이 3번을 하게 된다. 아까 앞에서 본 것 같이 2배가 늘고 몇 배가 늘지 않았다.
이런 걸 Constant Time이라고 부른다. 빠른 시간 복잡도라고 할 수 있다.
This is a constant time approach. / Constant Time = Awesome
다시 정리를 하면 다음과 같다.
Let's Review
We've discussed three different approaches to finding the largest difference in this list.
| operations for n items | Approach |
| 3 or 1 이 될수있다. | Compare first & last numbers |
| 2n | Find largest & smallest numbers |
| n제곱 | Compare all numbers |
시간 복잡도 계산한다고 했을 때 어떻게 표현하고 쓰인다면 Big-O Notation을 이용한다.
일반적으로 다음과 같은 표기법의 종류가 있다.
최상의 경우 : 오메가 표기법 ( Big-Ω Notation)
평균의 경우 : 세타 표기법 (Big-θ Notation)
최악의 경우 : 빅오 표기법 (Big-O Notation)
시간복잡도에는 개발자들의 실무영역에서는 항상 최악의 경우를 생각하기때문에 빅오 표기법을 사용한다.
Big-O표기법은 알고리즘의 전체 단계를 대수 용어로 변환 한 다음 문제의 전체 복잡성에 큰 영향을 미치지 않는 하위 상수 및 계수를 제외하는 방법입니다. 수학자들은 아마도 "전체적인 영향"을 고려한 공식을 선호할 수 있지만 개발자들에게는 시간을 절약하기 위해 방식을 단순화하여 사용한다.
| Big -O Notation | Operations for n items | Approach |
| O(1) | 3 or 1 | Compare first & last numbers |
| O(n) | 2n | Find largest & smallest numbers |
| O(n제곱) | n제곱 | Compare all numbers |
1. O(1) (constant)
입력데이터의 크기에 상관없이 언제나 처리속도는 동행하게 이루어진다.
ex) sorted Array search
2. O(log n) (logarithmic)
입력데이터의 크기가 커지더라도 처리속도가 크게 달라지지 않으며, 실행시간이 지날수록 처리해야 하는 데이터의 양이 절반으로 줄어드며 실행 시간은 증가하지만 속도는 감소한다.
ex) Binary search
3. O(n) (linear)
입력데이터의 크기에 비례해서 처리시간이 증가해 메모리의 사용이 정비례 한다(step : size = 1 : 1).
ex) search linked list, for문을 이용한 array 검색
4. O(n²) (quadratic)
입력데이터의 크기에 따라 걸리는 시간은 제곱에 비례한다.
ex) 이중 for문
5. O(C^n) (exponential)
문제를 해결하기 위한 단계의 수는 주어진 상수값 C의 n제곱이다.
ex) 피보나치 수열, recursion
Big-O 각 자료구조별 시간복잡도 분석
Array
배열은 값 모음을 저장할 수있는 기본 데이터 구조이다(원초적). 메모리 상에서 데이터 공간의 사이즈를 정해주면 그 사이즈를 할당 할 수 있는 공간을 찾아 할당해준다(Javascript 제외)
-
Lookup(position) O(1)
Array에 경우 데이터의 위치를 알고 있기 때문에 검색을 하지않고 바로 접근 할 수 있다. -
Assign O(1)
데이터를 덮어 씌울 때 또한 데이터의 위치를 알고 있기 때문에 바로 접근이 가능하다 -
Insert O(n)
: 데이터를 삽입하려 할 때 그 index의 공간을 확보해야 하기 때문에 다른 데이터들의 자리를 하나씩 옮겨야 한다 -
Remove O(n)
: insert와 마찬가지로 그 index의 데이터를 지우고 공간들을 하나씩 옮겨서 빈공간을 채워야 한다 -
Find O(n)
: 만약 데이터의 위치를 알고 있지 않다면, array의 index를 하나하나씩 살펴보아야 하며 최악의 경우 데이터의 갯수(n)만큼 찾아야 한다
Linked List
Array와 LinkedList의 차이점은 데이터를 저장하는 방식이다. LinkedList는 Array와 같이 데이터가 연속적인 구조가 아니라 랜덤적으로 공간이 배정되어 있다. 따라서 Linked List는 비 연속 데이터 구조이므로 값이 연속 된 블록이 아닌 메모리 전체에 저장된다. Linked List에 경우 head의 노드값을 꼭 알고 있어야 하며, 데이터를 제거할 시 제거하려는 노드의 연결을 끊어주고 그 노드는 garbage collector가 처리한다.
-
Lookup(position) O(n)
Linked List의 경우 random으로 주소를 알고 있기 때문에 바로 접근이 불가능하고 head부터 찾기 시작해야 한다. 따라서 원하는 노드가 나올때까지 찾아야 하며 최악의 경우 데이터의 갯수(n)만큼 검색해야 한다. -
Assign O(n)
: lookup과 마찬가지로 head에서부터 찾기 시작하며 최악의 경우 데이터의 갯수(n)만큼 검색해야 한다. -
Insert O(1)
: 만약 노드를 head 또는 tail에 붙인다면 바로 접근이 가능하다. 따라서 본인의 노드를 head 또는 tail에 연결하면 되므로 시간복잡도는 O(1) 이다
만약 중간에 삽입하는 경우 노드를 삽입하고자 할때 이미 삽입해야하는 위치를 알고 있기 때문에 삽입하고자 하는 노드 전 후를 연결시켜 주면 되므로 시간복잡도가 O(1)이 -
Remove
: 내가 지우고자하는 데이터의 위치를 알고있다 가정하였을 때 insert와 마찬가지로 head와 tail은 시간복잡도가 O(1) 이다
그러나 만약 데이터를 중간에 제거하는 경우 내가 삭제하려는 노드의 위치는 알지만 내 전후의 노드들을 서로 연결시켜줘야 할때 연결하려는 이전 노드를 알지 못하기 때문에 탐색시간이 걸린다(O(n)) -
Find O(n)
: Lookup과 마찬가지로, 첫 노드인 HEAD에서 출발하여 원하는 데이터가 나올 때까지 순서대로 다음 노드들을 살펴봐야 하기에 데이터의 양이 많아질수록 작업 시간이 늘어난다. O(n) -
doubly Linked List
doubly Linked List는 lookup, assign, insert, find의 경우 Linked List와 같이 O(n)이지만, remove의 경우 데이터의 위치를 모두 알고 있기 때문에 검색없이 바로 제거가 가능하다(O(1))
Tree
tree는 시작점인 root노드를 가지며 이어져있는 하위 노드인 children을 가진다.
만약 내가 데이터를 검색해야 한다면 root노드부터 시작하여 내가 원하는 데이터를 찾을때까지 하위 노드를 계속 내려가야한다.
최악의 경우 모든노드의 갯수(n)만큼 살펴보아야 한다.(O(n))
ex) 대표적인 트리구조는 DOM Tree
Binary Search tree
binary Search tree는 자식 노드가 부모노드에 최대 2개씩만 연결되어 있어 왼쪽가지에는 root, 부모노드보다 작은 값, 오른쪽에는 큰 값이 들어 있다.
따라서 검색을 할때 최소의 경우 root노드에서부터 검색을 비교하며 검색을 하지 않아도 되는 노드들은 거치지 않을 수 있기 때문에 검색할 노드에 양이 검색을 할때마다 반씩 줄게 된다 (O(log n))
하지만 Binary Search tree의 종류 중 편향이진트리는 데이터의 구조가 한쪽으로만 치우쳐 있어 Linked List처럼 연결되어 있기 때문에 최악의 경우 노드의 갯수(n)만큼 검색을 해야 한다 (O(n))
시간복잡도를 구하는 요령
각 문제의 시간복잡도 유형을 빨리 파악할 수 있도록 아래 예를 통해 빠르게 알아 볼 수 있다.
|
하나의 루프를 사용하여 단일 요소 집합을 반복 하는 경우 : O(n) |