(191119) 시간복잡도 (Time Complexity)

알고리즘 (Algorithm)

어떤 목적을 달성하거나 결과물을 만들어내기 위해 거쳐야하는 일련의 과정들을 의미

 

즉, 한 문제를 해결할 때 같은 결과를 내더라도 여러 알고리즘이 사용될 수 있다.

 

알고리즘은 각기 다른 모양과 형태를 갖고 있고, 개발자들은 문제를 해결할때 최대한 효율적으로 시간과 공간(메모리)를 사용하고 싶어 하기에 쓰인 알고리즘의 수행 시간과 메모리 사용량을 평가하여 최대한 걸리는 시간과 메모리를 적게 쓰려고 한다.

 

 

복잡도 (Complexity)

알고리즘의 수행 시간과 메모리 사용량을 평가하기 위해서 복잡도라는 개념을 사용한다.

 

- 시간 복잡도 (Time complexity)

알고리즘의 수행 시간 분석 결과

 

- 공간 복잡도 (Space complexity)

알고리즘의 메모리 사용량에 대한 분석 결과

 

 

시간 복잡도 (Time complexity)

여기에선 시간 복잡도에 대해서 알아보았다. 시간 복잡도를 분석하는 것은 어떤 알고리즘에 n개의 input이 있을 때 얼마나 시간이 걸리는 지를 분석하는 것으로 여기서 나온 결과를 Big-O 표기를 통하여 정의 한다.

(여기서 중요한 것은 n의 단위, 즉 가장 큰 영향을 주는 n의 단위를 가지고 정의)

 

 

Big-O 표기

시간 복잡도를 표현하는 식으로 대표적인 Big-O 표현식은 아래와 같다.

 

 

1. O(1) - 상수 시간 (constant) : n개의 input이 있을 때, 알고리즘이 문제를 해결 할 때 한 단계만 거친다.이말은 즉 n의 갯수가 계속 증가한다해도 실행 시간은 어떤 상수로 일정한 것을 말한다. (constant 그래프 모양)

 

ex) n개의 input에 대하여 연산 횟수가 1, 2 ,5 혹은 어떤 상수로 일정 -> O(1)

 

 

 

2. O(log n) - 로그 시간 (logrithmic) : n개의 input이 있을 때, 알고리즘이 문제를 해결하는데 걸리는 시간이 특정 요인에 의해서 점점 줄어든다. 즉, n의 갯수가 계속 증가할수록 실행 시간은 처음엔 증가하다가 점점 줄어든다 (log 그래프 모양)

ex) 이진 탐색 트리의 탐색 시간 -> 기준 노드의 값보다 크면 오른쪽 하위로 이동하여 왼쪽 하위트리를 탐색하지 않아도 되기 때문에

 

 

 

3. O(n) - 직선적 시간 (linear) : n개의 input이 있을 때, 알고리즘이 문제를 해결할 때 input 만큼의 시간이 걸린다. 즉 n의 갯수가 증가하면 그만큼 실행 시간도 증가한다. (1차함수 그래프 모양)

 

ex) for문 등 ,  예를들어 2n + 5의 연산 횟수가 나오면 상수는 n보다 차수가 낮고, 앞의 계수는 생략하여 O(n)으로 표기)

 

 

 

4. O(n^2) - 2차 시간 (quadratic) : n개의 input이 있을 때, 알고리즘이 문제를 해결할 때 input 의 제곱만큼의 시간이 걸린다. 즉, n의 갯수가 증가할수록 실행 시간이 증가하는데 점점 급격하게 증가한다.. (2차함수 그래프 모양)

 

ex) 이중 for문, 예를들어 3n^2 + 2n +1 의 연산 횟수가 나오면 표기는 O(n^2)

 

 

5. O(C^n) - 지수 시간 (exponential) : n개의 input이 있을 때, 알고리즘이 문제를 해결할 때 어떤 주어진 상수의 n제곱 만큼 시간이 걸린다. 즉, n의 갯수가 처음에 그렇게 크지 않아도 실행 시간이 엄청 걸리고 매우 급격하게 증가한다. (지수함수 모양)

 

 

자료구조의 시간 복잡도

먼저 자료구조의 시간 복잡도를 분석하기 전에, 같은 함수(메소드)라도 자료 구조의 상황에 따라 시간 복잡도가 달라질 수 있다.

이때 가장 좋은 경우를 Best case, 가장 안 좋은 경우를 worst case, 그리고 보통의 상황을 avearage case라고 한다.

(보통 최악의 경우를 생각을 해야하므로 worst case로 나타낸다)

 

 

Stack - 후입선출

1. 데이터를 넣는 경우 - 맨 위(top)에 쌓기만 하면 되므로 O(1)

2. 데이터를 삭제하는 경우 - 맨 위(top)의 데이터를 바로 삭제하면 되므로 O(1)

3. 데이터 탐색의 경우 - 현재 맨 위(top)의 데이터가 무엇인지 바로 확인하면 되므로 O(1)

 

그외 - stack이 비었는지, stack의 사이즈 확인은 현재 top을 통해 바로 확인이 되므로 O(1)

 

 

Queue - 선입선출

 

1. 데이터를 넣는 경우 - 현재 데이터들의 맨 뒤에 넣으면 되므로 O(1)

2. 데이터를 삭제하는 경우 - 현재 데이터들의 맨 앞 데이터를 삭제하면 되므로 O(1)

3. 데이터의 탐색의 경우 - 현재 데이터들의 맨 앞 데이터를 바로 확인하면 되므로 O(1)

 

그외 - queue가 비었는지, queue의 사이즈 확인은 stack 과 마찬가지로 데이터의 삽입과 삭제할 때 count를 통하여 바로 확인이 되므로 O(1)

 

 

배열 - 배열의 크기를 미리 선언

 

1. 데이터를 넣는 경우 - 배열이 비어있거나 배열에 여유공간이 있고 맨 뒤에 넣거나 하는 경우에는 최상의 경우로 O(1)이겠지만, 보통은 어떤 데이터를 배열의 특정 index에 넣으면 기존에 있던 값들을 한칸씩 뒤로 옮겨줘야 하므로 최악의 경우 O(n)의 시간이 걸린다. 그래서 O(n)!!!!

 

2. 데이터를 삭제하는 경우 - 삽입과 마찬가지의 이유로 O(n)

 

3. 데이터의 탐색 - 특정 데이터를 찾으려면 배열의 처음 index부터 하나씩 확인하여야 하므로 O(n)

 

4. lookup - 배열은 index에 데이터를 저장하고 있으므로 특정 index를 통해 바로 확인이 되므로 O(1)

 

 

Linkde list (연결리스트) - 단순 연결 리스트의 경우

 

1. 데이터의 탐색 - 연결리스트이 맨 앞인 head부터 찾으려는 데이터까지 순차적으로 확인하여야 하므로 최악의 경우 O(n) 

 

2. 데이터의 삽입 - 현재 넣으려는 위치의 노드를 알고 바로 접근이 가능한 경우에 삽입을 하므로 이때 삽입만 보면 해당 노드의 '다음'에 넣는 경우는 다음을 가리키는 노드를 알고있기 때문에 보통 O(1), 연결리스트의 맨 앞이나 맨 뒤에 넣는 것도 head와 tail을 알고 있기 때문에 O(1), 즉 연결리스트에서 삽입은 보통 O(1)이 걸린다고 생각

(해당 노드의 '전'에 넣는 경우에는 그 해당 노드를 가리키는 노드의 탐색이 필요하기 때문에 최악의 경우O(n), 이때 이중연결리스트는 노드의 전 노드도 가리키기 때문에 O(1)이 걸린다) 

 

3. 데이터의 삭제 - 맨 앞이나 맨 뒤 데이터의 삭제는 head와 tail을 알고 있기 때문에 O(1), 리스트의 중간에 있는 데이터를 삭제하려면 그 '전'노드까지 탐색이 필요하기 때문에 O(n)

 

4. lookup - 탐색과 마찬가지로 O(n)

 

 

Graph (그래프) - 무향 그래프의 경우

그래프의 기본적이고 핵심적인 연산은 어떤 노드의 인접한 노드를 찾는 연산과 어떤 두 노드가 연결되어있는지 확인하는 연산이다.

어떤 그래프를 어떤 방법을 구현하냐에 따라 시간복잡도의 효율이 다를 거라고 생각됨

 

인접 행렬로 구현한 그래프

 

1. 인접한 노드를 찾는 경우 - 인접 노드를 찾기 위해서는 한 행을 전부 읽어야하므로(모든정점을 순회) O(n)

 

2. 어떤 두 노드가 연결되어있는지 확인하는 경우 - 행렬을 통해 존재 여부를 바로 확인할 수 있으므로 O(1)

 

3. 그래프에 존재하는 모든 간선의 수 - O(n^2) (행렬을 전부 봐야하므로..?)

 

인접 리스트로 구현한 그래프

 

1. 인접한 노드를 찾는 경우 - 노드의 연결 리스트를 탐색하여야 하므로 O(v(노드의 연결리스트의 길이))

(최악의 경우에는 O(n)까지 걸릴 수 있겟네????)

 

2. 어떤 두 노드가 연결되어있는지 확인하는 경우 - 위와 마찬가지의 경우로 O(v(노드의 연결리스트의 길이))

(이것도 마찬가지로 최악의 경우에는 O(n)??)

 

3. 그래프에 존재하는 모든 간선의 수 - O(n+e) (노드 + 간선의 수만큼)

 

 

 

 

Tree (트리) - 이진탐색트리

 

이진탐색트리에서의 탐색의 경우 - 평균적으로 O(log n) 의 시간복잡도를 가지지만 이진 탐색트리의 데이터들이 한쪽으로 극단적으로 치우친 경우(마치 연결리스트 처럼되면)에는 최악의 경우 O(n)의 시간복잡도를 가질 수 있다.

 

(삽입, 삭제의 경우 탐색을 base로 하기 때문에 탐색과 같은 시간복잡도???)

 

 

 

Hash Table (해시 테이블)

해시 함수 자체의 시간복잡도는 고려하지 않고 해시 테이블의 시간복잡도만 고려

 

1. 데이터의 삽입 - 해시 함수를 통해 해당하는 해시를 index로 배열에 바로 값을 저장하므로 평균적으로 O(1)

(해시 충돌이 일어나 최악의 경우 모든 저장소를 순회해야 할 경우 O(n)이 나올 수 있다)

 

2. 데이터의 삭제 - 해시 함수를 통해 해당하는 해시를 index로 배열에서 값을 바로 제거하면 되므로 평균적으로 O(1)

(이 경우도 삽입과 마찬가지로 최악의 경우 O(n))

 

3. 데이터의 탐색 - 해시 함수를 통해 해당하는 해시를 index로 배열에서 바로 값을 확인하면 되므로 평균적으로 O(1)

(이경우도 마찬가지 최악의 경우 O(n))

 

해시 충돌이 일어날 경우 해시 충돌 해결법에는 분리연결법, 개방 주소법이 있다.

 

분리 연결법의 경우

- 최악의 경우 특정한 해시에 자료들이 몰려서 연결 리스트 탐색을 하는 것과 같을 수 있기 때문에 O(n)

 

개방 주소법의 경우

- 최상의 경우에는 해시 함수를 통해 얻는 해시가 바로 비어 있는 경우 O(1), 최악의 경우에는 비어있는 해시가 나올 때까지 계속 찾아가야하므로 O(n)