Time Complexity
Published in
3 min readApr 5, 2020
#TIL
Time Complexity ( 시간복잡도 )
: 알고리즘의 시간복잡도 (Time complexity)란, 함수가 입력된 값을 처리하는데 걸리는 시간을 측정한 값이라고 한다.
따라서 시간복잡도가 높아질수록 알고리즘이 수행되는 시간이 길어지는 것이기 때문에, 시간복잡도가 낮은 효율적인 알고리즘을 만들기 위해 노력해야한다.
그리고 시간복잡도는 Big-O 표기를 이용하여 정의할 수 있다.
Big-O Notation
<대표적인 시간복잡도>
O(n)(constant time), O(log(n)), O(n)(linear time) , O(n log(n)), O(n²), O(n³), O(2^n)(exponential time), O(n!), O(c^n)등으로 표현한다.
- O(1)- 상수시간 : 입력값 N이 주어졌을 때, 알고리즘이 문제를 해결하는데 오직 한 단계만을 거친다.
ex) var arr = [1,2,3,4,5]
arr.pop() // 5값을 검색할 때, 배열에서는 해당 인덱스 그리고 객체에서는 키를 알고 있다면 한 단계만을 거칠 있다.
2. O(log n)- 로그시간: 문제를 해결하는데 필요한 단계들이 연산마다 특정 요 인에 의해 줄어들게 된다.
배열에서 값을 찾고자 할때, 어느쪽에서 시작할지를 알고 있다면 검색시간이 2배로 줄어들게 된다.
ex) Binary Tree 에서 값에 접근하고자 할 때, O(log n) 이 걸리지만, 자료구조를 잘못프로그래밍하게 된다면 unblance 하게 될 경우에는 O(n)-leaner 만큼 걸리게 될 수도 있다. 3. O(n)-직선시간: 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가진다.
ex) 자료구조 Linked List 에서 특정 데이터를 찾기 위해서는, 그 데이터를 찾을 때까지 순회를 해야하기 때문에 O(n)-leaner 만큼 걸리게 된다. 배열에서는 특정 값을 찾고자할때 인덱스를 알고있다면 0(1)만큼 걸리지만, 특정 값의 위치를 모른다면 배열안의 모든 값들을 순회해야하기 때문에 O(n) 만큼 걸릴 수 있다.
4. O(2^N)- 지수 시간: 문제를 해결하기 위해 모든조합과 방법을 시도할 때 사용된다.
