시간복잡도, 공간복잡도

시간복잡도

시간복잡도

 1) 알고리즘을 실행할 때 걸리는 절대적인 시간이 아닌 알고리즘에서 수행하는 연산의 횟수.

 2) 입력값과 문제를 해결하는데 걸리는 시간과의 상관관계

 3) 각 줄이 실행되는 것을 1번의 연산이 된다고 생각.

 4) 최악의 경우의 연산값을 알 수 없는 경우에는 배열의 길이(N)

 5) 최악의 경우의 연산값을 알 수 있는 경우에는 그 값(상수)

 6) 시간복잡도 = CPU 효율과 관련

---

점근 표기법

Big O 표기법

 1) 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴지.

 2) 시간복잡도 함수 : T(N)

 3) T(N)에서 최고차항만 남기고 최고차항의 계수를 버리고 표현. (상수를 버림)

 4) 

 - O(1) : 상수시간 알고리즘. 인풋 사이즈와 관계없이 스텝이 정해진 알고리즘. 문제를 해결하는데 오직 한단계만 처리함.

 - O(N) : 직선적 시간 알고리즘. 문제를 해결하기 위한 단계의 수와 입력값 N이 1:1 관계를 가짐.

                * 최악의 경우의 연산값을 알 수 없는 경우 N

 - O(N^2) : 2차시간 알고리즘. 문제를 해결하기 위한 단계의 수는 입력값 N의 제곱. 루프 안에서 루프를 실행. 배열의 각 아이템에 대해 루프를 반복 실행. (중첩 반복)

 - O(log N) : 선형로그형. 문제를 해결하기 위한 단계의 수가 n*(log2n) 번 만큼의 수행시간을 가진다.

 

Big Omega 표기법

 - 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴지.

 - 입력값의 분포에 따라 성능이 변화할 수 있다.

    ex. 찾고자 하는 원소가 배열의 맨 처음에 있으면 1번만 연산하면 된다.

          찾고자 하는 원소가 배열의 맨 끝에 있다면 그 배열의 길이(N)만큼 연산해야 된다.

 - 입력값이 최선의 경우는 거의 없고 최악의 경우를 대비해야 한다.

 

따라서, 최악의 경우 시간이 얼마나 소요될지(Big O)에 대해 고민하자.

---

공간복잡도

 - 입력값과 문제를 해결하는데 걸리는 공간과의 상관관계

 - 저장하는 데이터의 양이 1개의 공간을 사용

 - 공간복잡도 = RAM 효율과 관련

 - 공간복잡도는 모두 상수라 알고리즘의 성능이 공간에 의해서 결정되지 않는다.

 

따라서 시간복잡도를 더 신경 써야 한다. 공간을 희생해서라도 시간복잡도를 줄여야 한다.

---