[자료구조] 복잡성

시간 복잡도

시간 복잡도는 서로 다른 알고리즘의 효율성을 비교할 때 사용 

- Rule 1:  input  \geq≥  0

- Rule 2: functions do more work

             for more input

- Rule 3: drop all constants

- Rule 4: ignore lower order terms

- Rule 5: ignore the base of logs

-  2n = O(n)2n=O(n) =>  2n \in O(n)2n∈O(n) 

 

규칙 1. 입력값(n)은 항상 0보다 크다.

: 입력값이 음수일 수는 없다.

: 복잡도는 항상 0보다 크다고 가정하고 계산

 

규칙 2. 함수는 많은 입력값이 있을 때 더 많은 작업을 하게 된다.

: 더 많은 입력값이 주어지면 어떤 작업을 하는 데 필요한 계산이나 처리 시간이 길어진다.

 

규칙 3. 시간 복잡도에서는 모든 상수를 삭제한다.

: 만약 어떤 알고리즘의 복잡도가  3n 이라면 3은 고려하지 않고 시간 복잡도는 n이 된다.

:  2n, 3n, 10n 모두 복잡도가 n인 알고리즘이다.

 

규칙 4. 낮은 차수의 항들은 무시한다.

: 시간 복잡도에서는  n과 n^2을​dmf 비교할 때에는 항상 n^2이 더 오래 걸리는 알고리즘이라고 판단한다.

: 여기서 의문이 들 수 있는 점은 그래프에서 (1,1)인 지점 전까지는  n이 더 오래 걸릴 수 있다는 것

: 하지만 알고리즘에서는 입력값( n )이 1보다 작은 값은 고려하지 않고 큰 값에 대해서만 생각을 하므로  n이 무한으로 커진 경우를 가정하고 비교해야 한다.

: 이런 이유로 시간 복잡도에서는 낮은 차수의 항들은 무시

: n^3 + n^2 ​​+n 이라는 함수가 있을 때,  n 과 n^2은 알고리즘의 시간 복잡도에 영향을 미치지 않고, 입력값이 무한이 될 때 고려해야 할 부분은  n^3​​이다.

 

규칙 5. 시간 복잡도 함수가 log 함수를 포함할 경우 밑은 무시한다.

: 모든 로그는 서로 배수 관계

: 복잡도에 관해서 이야기할 때는 로그의 밑에 대해서는 고려하지 않아도 된다.

: 로그의 밑은 무시하고 로그 ( logn) 알고리즘이라고만 말하면 된다.

: 복잡도가  log 인 알고리즘은 보통 무언가를 반으로 나누거나 2를 곱한 경우에 자주 사용된다.

: 만약 for 반복문을 사용해서 무언가를 탐색하면서 반으로 나누거나 2를 곱할 때 복잡도는 밑이 2인 로그가 된다.

: 10으로 나누거나 10을 곱하게 되면 밑이 10인 로그가 된다.

: 하지만 시간 복잡도를 표시할 때에는 로그의 밑은 무시하고 그냥 log n 복잡도를 가진다고 표현한다.

 

규칙 6. 등호를 사용하여 표현한다.

: 2n은 O(n)과 같다.

: O(n)은  2n이 어떤 함수의 집합에 속한다는 의미를 가진다.

: 그렇기 때문에 아래와 같은 등호를 활용하여 이 관계를 수학적으로 쓸 수 있다.

2n = O(n),  2n ∈ O(n)

 

자바로 구현하고 배우는 자료구조