자료구조(java) 1_1. 복잡성 소개

1-1 복잡성 소개

알고리즘의 규칙

1. input >= 0 (입력값은 항상 0보다 크다.)(복잡도는 항상 0보다 크다.)

음의 입력값은 시간 복잡도를 고려했을 때 말이 되지 않는 경우.

1. function은 많은 input이 있을 때 더 많은 작업을 하게 된다.

1. 시간 복잡도에서는 모든 상수를 삭제한다.(항상 상수는 무시한다.)

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

즉, 2n, 3n, 10n 모두 복잡도가 n 인 알고리즘인 것.

1. 큰 숫자만 고려한다.

알고리즘에서는 1보다 작은 수는 신경쓰지 않는다.

알고리즘의 시간 복잡도에 영향을 미치는(무한히 커진 값들) 값만 주목한다.

ex) n^3+n^2+n+5 라는 함수는 곧 “n^3알고리즘” 이라고 말한다.

​

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

모든 로그는 서로 배수 관계이다. 그래서 복잡도에 관해서 이야기할 때는 로그의 밑에 대해서는 고려하지 않아도 된다. 로그의 밑은 무시하고 로그 ( logn ) 알고리즘이라고만 말하면 된다.

로그함수는 지수함수의 역함수.

2^3 = 8 👉 “2를 및으로 하는 8의 로그는 3과 같다.”

1. 등호를 사용하여 표현한다.(2n=O(n) => 2n \in O(n)2n∈O(n) )

2n2n 은 O(n)O(n) 과 같다. 여기서 O(n)O(n) 은 2n2n 이 어떤 함수의 집합에 속한다는 의미를 가짐. 그렇기 때문에 아래와 같은 등호를 활용하여 이 관계를 수학적으로 쓸 수 있다.

생각해보기

1)시간 복잡도가 1이거나 n인 것은 각각 무엇을 의미할까요?

시간 복잡도 1 : 입력값(n)의 크기와 관계 없이 수행하는 시간이 일정함.

시간 복잡도 n : 입력값(n)의 크기에 따라 수행 시간이 같은 비율(n만큼)로 증가.

References

자바로 구현하고 배우는 자료구조 -Rob Edwards (boostcourse)