01. 자료구조 스터디 _ with java

1. 시간 복잡도

: 시간 복잡도는 서로 다른 알고리즘의 효율성을 비교할 때 사용하며 몇가지 규칙이 있다

 

- input  ≥  0

- functions do more work

             for more input (입력값이 많을 수록 많은 처리해야함)

- drop all constants (상수 무시)

- ignore lower order terms (낮은 차수 무시)

- ignore the base of logs ( 로그는 서로 배수관계 (계산할때 나누면됨) 이므로 -> 로그의 밑은 무시하고 log n 알고리즘이라 말함)

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

 

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

- 입력값이 음수일 수는 없으며, 그래서 복잡도는 항상 0보다 크다고 가정하고 계산을 해야함

 

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

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

 

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

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

- 2n, 3n, 10n 모두 복잡도가 n인 알고리즘임

 

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

- 시간 복잡도에서는 n과 n^​2을 비교할때에는 항상 n^2이 더 오래 걸리는 알고리즘

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

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

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

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

 

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

- 모든 로그는 서로 배수 관계임, 그래서 복잡도에 관해서 이야기 할 때는 로그의 밑에 대해서는 고려하지 않아도 됨

- 로그의 밑은 무시하고 로그(logn)알고리즘이라고만 말하면됨