Time Complexity & Data Structure 시간복잡도와 자료구조
Complexity Analysis — Time Complexity 시간복잡도
Complexity Analysis 복잡도 분석
복잡도 분석이란 ?
알고리즘을 푸는데 있어서 시간과 공간을 얼마나 차지하는지 나타내는 것이다.
즉, 알고리즘이 얼마나 효율적인지를 분석하는 것이고 그 지표로 공간 복잡도와 시간 복잡도가 있다. 시공간이 무한이라면 개발자들은 좋은 코드에 대해 고민하지 않아도 될지도 모른다, 하지만 제한적인 시공간안에서 보다 효율적인 프로그래밍을 해야하는 개발자들에게 Complexity Analysis는 당연히 중요하고 염두해야한다.
Time Complexity
그럼 Time Complexity, 시간 복잡도에 대해서 예시를 통해서 알아보자.
Example) find the largest difference in a list of numbers
숫자가 여러개 들어있는 배열에서 두 수의 차가 가장 큰 것을 찾는다고 가정하자. 우리는 이 문제를 해결하기 위해 알고리즘을 짤 것이다. 일반적으로 배열의 크기가 크면 이 알고리즘을 수행하는데에 더 많은 시간이 걸린다고 생각할 수 있다. 하지만 알고리즘에 따라서 문제의 크기와 시간 복잡도는 정비례하지 않고 아예 비례하지 않을 수도 있다.
알고리즘 1: 모든 숫자들의 차를 다 구해본다. (모든 경우의 수를 확인)
2부터 16까지 들어있는 배열이 주어졌다고 가정했을 때, 위와 같이 표를 만들어서 모든 수의 차를 구할 수 있다. (sorted array인지 아닌지 모른다고 가정)
이 경우 총 n²번 연산을 하게 된다. 배열안에 2-16까지 숫자가 총 15개 있으므로, 이 알고리즘으로 문제를 풀 때 우리는 총 225번 연산을 하게 된다.
알고리즘 2: 가장 큰 수와 가장 작은 수를 확인한다.
이 경우 가장 처음의 숫자를 가장 큰수이자 가장 작은 수라고 정의해놓고 작은 수를 가려내는 연산을 n번, 가장 큰 수를 가려내는 연산을 n번, 총 2n번의 연산을 한다.
알고리즘 3: 만약 sorted array 였다면?
그럼 그냥 맨 앞의 숫자와 맨 뒤의 숫자의 차이를 구하면 되니 연산은 1번 한다. (차를 계산해주는 것 까지하면 3번..이지만 앞서 두 케이스에서 그렇게 하지 않았으므로 1번이라고 하겠다.)
그럼 각 알고리즘 케이스들의 시간복잡도는 어떻게 될까?
Big-O Notation
시간 복잡도를 나타낼 때 Big-O Notation이라는 것을 사용한다. 이것은 시간 복잡도를 나타내기위해 약손된 기호같은 것이라고 생각하면 된다. 알고리즘의 최악의 경우의 수를 O( ) 에 넣어준다고 생각하면 된다.
- 알고리즘 1: 연산 횟수 = n², Big-O Notation = O(n²)
- 알고리즘 2: 연산 횟수 = 2n, Big-O Notation = O(n)
- 알고리즘 3: 연산 횟수 = 1, Big-O Notation = O(1)
알고리즘2 의 Big-O Notation을 보면 왜 2n이 아니지 하는 의문이 들 수 있다.
Big-O Notation은 일반적인 complexity types, 복잡도 종류를 나타내는 것이지 정확한 연산 공식을 나타내는 것이 아니다. 그러므로 대략의 time complexity 를 나타내기 때문에 상수가 생략된다. 아래 수직선에서 time complexity 종류를 알 수 있다. 왼쪽으로 갈수록 시간복잡도가 좋고, 오른쪽으로 갈수록 좋지 않다.
Time Complexity Types
— O(1), constant
실행 시간이 항상 똑같을 때 시간복잡도는 constant.
대표적인 예: Array[i] 검색, Hashtable에 데이터 추가
— O(log n), logarithmic
실행 시간이 데이터의 크기만큼 늘어나지만 늘어나는 정도는 점차 줄어든다.
대표적인 예: Binary Search 이진 탐색
— O(n), linear
실행 시간이 데이터의 크기와 정비례한다.
대표적인 예: Array나 Linked List에서 Linear로 찾을 때
— O(n²), quadratic
실행 시간이 데이터의 크기가 늘어남에 따라 같이 증가하고, 그 증가율또한 증가한다. 데이터가 클수록 시간복잡도는 점점 더 빠르게 증가한다.
대표적인 예: constant time operations inside two nested for-loops
— O(c^n), exponential
실행 시간이 기하급수적으로 증가한다.
대표적인 예: n글자 비밀번호를 추측하는 경우
Data Structures & Time Complexity
각 자료구조의 시간 복잡도와 공간 복잡도를 한눈에 볼 수 있는 컨닝페이퍼이다.
시간복잡도를 찾아보다가 자바스크립트로 자료구조가 잘 구현되어있는 블로그를 봐서 공유해본다.
