complexity

Complexity (=복잡도)

Time complexity와 Space complexity가 있다.

복잡도를 설명하기위해서 Big-O notation을 이용한다.

Big-O notation : Complexity를 설명하는 도구, 근사치를 가지고 이야기를 하기때문에 표기법 O(n) 이런식으로 표기된다.

1. Time Complexity. : 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 나타냄.(알고리즘에 사용되는 연산 횟수의 총량)

   1) O(1) : 언제사용 ? array lookup, hash table insert, 하나의 키에 접근하는 방식.

   2) O(logn) : 언제사용 ? binary search 할 때  

   3) O(n) : 언제사용? 배열을 포문에 한번 돌릴때. 

   4) O(nlogn) :   Quick sort, Merge sort, Heap sort 에 사용 

   5) O(n^2) : 2중 배열사용 할 때, => 전체 데이터와 비교할때 사용함. 통상, Insertion sort, Bubble sort, Selection sort

   6) O(c^2) : 사용하면 거의 버그급이지만, 주로 패스워드 만들때 사용한다.  패스워드가 길면 길수록 찾기가 어렵기때문임. 

효율성(런타임 속도) 은 1번으로 갈수록 좋다. 반면 6번으로 갈수록 처리하는데 시간이 오래걸린다.

2. Space complexity : 알고리즘에 사용되는 메모리 공간의 총량임.