반응형 Development/Algorithm1 시간복잡도, 공간복잡도 시간 복잡도 왜 필요한가? - 정의 : 작동하는 알고리즘의 수행 시간을 정량화하는 것 - 가정 : 1초에 1억번 연산을 한다고 가정 - 문제 : 제한시간 10초의 문제가 있을 때 연산량을 10억 번 이하로 줄여야 하며 설계시에 시간 복잡도가 높으면 미리 낮추어야 함 - T(N)은 최악의 경우에만 연산횟수를 나타냄 예를 들어 N번 연산이 2번 필요한데 하나는 N번이 필수고, 다른 하나는 조건에 의해 최소 0~최대 N번의 연산이 필요할 때 Worst 케이스로 2N으로 표기 시간 복잡도 표기법 - 빅오 O(N) 표기법 : worst case 연산 횟수 표기 - 빅오메가 Ω(N) 표기법 : best case 연산 횟수 표기 - 빅세타 θ(N) 표기법 : 평균 case 연산 횟수 표기 일반적으로 빅오 표기법 사용.. 2021. 7. 9. 이전 1 다음 반응형