시간복잡도와 공간복잡도
알고리즘을 평가할 때는 두가지 요소로 측정한다. 첫째는 시간복잡도, 둘째는 공간복잡도
시간 복잡도는 말 그대로 알고리즘을 수행하는데 걸리는 시간이다. 즉, 수행시간이다.
공간 복잡도는 알고리즘의 메모리 사용량을 말한다.
알고리즘을 평가할 때 고려해야할 점은 알고리즘이 최악의 경우로 돌아가게 되는 것을 기준으로 해야한다는 것이다. 그 이유는 worst case를 사용해야 다른 요소들이 순수한 알고리즘만 평가하는 데 방해를 하지 않기 때문이다.
예를 들어, 리스트에서 해당되는 값을 찾아내는 알고리즘이라고 하자. 이럴 경우 찾으려는 아이템이 리스트의 첫번째에 위치하는 경우면 바로 찾을 수 있고 시간도 절약되니까 좋겠지만, 아이템이 리스트의 어느 위치에 있을지는 아무도 모르기 때문에 평가를 하기에는 적합하지 않다. 따라서 최악의 경우로 평가를 한다.
오늘은 다양한 자료구조들의 함수 별 시간 복잡도에 대해서만 알아보겠다.
자료구조 클래스들의 member function은 이전 포스트들에서 구현한 멤버 함수들을 기준으로 설명하겠다.
stack: josushell.tistory.com/3?category=427367
queue: josushell.tistory.com/4?category=427367
비정렬 리스트: josushell.tistory.com/5?category=427367
정렬 리스트: josushell.tistory.com/6?category=427367
Big O notation (빅오 표기법)
알고리즘의 성능을 표기할 때 다른 표기법들도 많은데 왜 굳이 big O를 사용할까
그것은 바로 빅오표기법이 알고리즘의 상한선을 기준으로 하기 때문이다.
예를 들어 어떤 알고리즘의 시간 복잡도를 나타낸 함수가
라고 하면
Big O notation으로 표기한 시간 복잡도는
가 된다.
최고차항을 제외한 나머지는 버리고, 즉 상한선을 기준으로 표기한다.
빅오 표기법은 두가지 특징이 있다.
1. 상수항은 무시한다
-> 시간 복잡도 함수가 2N인 경우 빅오 표기법으로는 O(N)이다.
2. 최고차항만 표기한다.
-> 앞서 말했듯이 영향력이 없는 항들은 제외하고 최고차항만 표기한다.
Stack의 시간복잡도
| stack memebr function | Array Based | Linked List |
| 생성자 | O(1) | O(1) |
| 소멸자 | O(1) | O(N) |
| full | O(1) | O(1) |
| empty | O(1) | O(1) |
| push | O(1) | O(1) |
| pop | O(1) | O(1) |
| top | O(1) | O(1) |
O(1) - 상수시간: 알고리즘이 문제를 해결하기 위해서 한 단계만 거침
O(N) - 직선시간: 입력값과 문제 해결을 위한 단계가 1:1
Array based stack은 단순히 top 숫자 연산으로 이루어지기 때문에 시간 복잡도가 O(1)이다.
Linked List stack은 소멸자가 중요하다. heap영역의 모든 new를 할당해제 해줘야하기 때문이다. 따라서 데이터가 N개 있을 때 N번의 delete가 필요하기 때문에 시간 복잡도는 O(N)이다. 나머지는 전부 연산이 한번씩 이루어진다. 이 때 연산의 기준은 코드의 줄 수가 아니라 함수가 끝날 때까지 몇번의 작업을 하는가에 달려있다.
Queue의 시간복잡도
| queue member function | Array Based | Linked List |
| 생성자 | O(1) | O(1) |
| 소멸자 | O(1) | O(N) |
| full | O(1) | O(1) |
| empty | O(1) | O(1) |
| push | O(1) | O(1) |
| pop | O(1) | O(1) |
stack과 동일한 이유로 소멸자만 O(N)이고 나머지는 상수시간이다.
비정렬 리스트의 시간복잡도
| unsorted member function | Array Based | Linked List |
| 생성자 | O(1) | O(1) |
| 소멸자 | O(1) | O(N) |
| full | O(1) | O(1) |
| empty | O(1) | O(1) |
| length | O(1) | O(1) |
| reset | O(1) | O(1) |
| get | O(1) | O(1) |
| retrieve | O(N) | O(N) |
| insert | O(1) | O(1) |
| deleted | O(N) | O(N) |
Array based 비정렬 리스트에서 retrieve deleted 이 함수들은 데이터를 찾는 과정이 필요하다. 찾아서 반환 혹은 삭제를 해야하기 때문에 최악의 경우는 데이터가 N개일 때 N번을 찾는 것이다. 따라서 시간 복잡도는 최악의 경우인 O(N)이다.
정렬 리스트의 시간복잡도
| sorted member function | Array Based | Linked List |
| 생성자 | O(1) | O(1) |
| 소멸자 | O(1) | O(N) |
| full | O(1) | O(1) |
| empty | O(1) | O(1) |
| length | O(1) | O(1) |
| reset | O(1) | O(1) |
| get | O(1) | O(1) |
| retrieve | O(N) / O(log N) | O(N) |
| insert | O(N) | O(N) |
| deleted | O(N) | O(N) |
O(log N) - 로그시간: 문제를 풀 때 특정 요인에 의해 필요한 단계들이 줄어듬
오늘의 포인트는 정렬 리스트
지난 포스트에서 Array based 정렬 리스트는 이진탐색을 사용해서 구현했다. 따라서 이진탐색으로 retrieve를 구현한다면 시간 복잡도는 O(log N), 아니면 O(N)이다.
왜 이진탐색의 시간 복잡도가 O(log N)인지 증명이 궁금하다면 josushell.tistory.com/6 참고
여기서 질문이 나올 수 있다.
▶ insert, deleted 또한 이진탐색으로 구성했는데 왜 시간 복잡도는 O(log N)이 아닌 O(N)인가?
insert와 deleted를 이진탐색으로 구현한 것은 추가 혹은 삭제할 데이터의 위치를 찾은 것이다.
insert의 경우, 추가할 위치를 찾은 후에는 그 위치의 뒤에 있는 데이터들을 전부 한 칸씩 밀어내서 추가할 데이터의 자리를 마련해야한다. 한 마디로 리스트들이 방 빼줘야함
deleted의 경우에도 마찬가지로, 삭제할 아이템의 위치를 찾았다면 그 뒤에 있는 데이터들을 한 칸씩 앞당겨야한다.
그래서 최악의 경우를 따지자면 추가할 위치가 맨 처음이라 데이터를 N번 뒤로 밀어내는 경우, 삭제할 데이터가 맨 처음이라 데이터를 N번 당겨와야 하는 경우이므로 O(N)이다.
원래는 N+logN 이지만 최고차항만 표기한다는 빅오 표기법에 따라 어짜피 O(N)인 것이다.
Linked List 로 구현한 정렬 리스트도 비정렬 리스트와 마찬가지인 이유로 소멸자, retrieve 함수 모두 시간 복잡도가 O(N)이다.
'STUDY > 자료구조' 카테고리의 다른 글
| [자료구조] stack, queue, sorted list, unsorted list (0) | 2020.10.21 |
|---|---|
| [자료구조] 정렬 리스트 Array based vs Linked List (0) | 2020.10.19 |
| [자료구조] 비정렬 리스트 Array based vs Linked List (0) | 2020.10.18 |
| [자료구조] Queue - Array based vs Linked List (0) | 2020.10.17 |
| [자료구조] stack- Array based vs Linked List (0) | 2020.10.16 |