자료구조
자료구조 - 복잡성(Complexity)
BSYeop
2022. 8. 11. 17:38
시간 복잡도
- 서로 다른 알고리즘의 효율성을 비교할 때 사용
규칙 1. 입력 값(n)은 항상 0보다 크다.
규칙 2. 함수는 많은 입력값이 있을 때 더 많은 작업을 한다.
규칙 3. 시간 복잡도에서는 모든 상수를 삭제한다.
- 시간 복잡도가 3n이라면 복잡도가 n인 알고리즘 이다. 2n,5n,10n 모두 복잡도가 n인 알고리즘이다.
규칙 4. 낮은 차수의 항은 모두 무시한다.
- 시작 복잡도에서 n과 n² 를 비교할 때 n² 이 항상 더 오래걸리는 알고리즘으로 판단한다..
- n³ + n² + n의 시간 복잡도는 n³인 알고리즘이다.
규칙 5. 시간 복잡도 함수가 log를 포함할 경우 밑은 무시한다.
규칙 6. 등호를 사용하여 표현한다