[자바 자료구조] Complexity, 시간복잡도

 

본 게시물은 아래 인강의 내용을 기반합니다.

네이버에서 제공하는 고퀄리티 강의인데다

무려 무료..!라 저처럼 공부하고자 하는 사람들에게 강추합니다

 

https://www.boostcourse.org/cs204

 

 

---

[Complexity]

시간복잡도, 복잡도의 몇가지 준수 사항이 있으며 이는 아래와 같음

1. input 은 0보다 크거나 같다, 음의 입력값에 대한 시간복잡도는 고려하지 않는다

​

2. function은 input이 커지면 커질수록 더많은 작업(work)을 한다

→ 더 큰 input이 있으면 있을수록 더 많은 work를 하는 상승 곡선의 형태를 띔을 의미

​

3. 알고리즘의 복잡도의 모든 상수는 제거 한다

→ 3n = n = 10000n 모두 같은 복잡도로 판단한다

​

4. 우리는 가장 큰 숫자(복잡도)만 고려하며, 그외는 무시한다

→ n^3 + n^2 의 복잡도 식이 있을때, 우리는 가장 큰 n^3만 고려하며 아래는 절사

​

​

​

각기호에 대해 설명하면 다음과 같음

 

 

[복잡도 기호]