시간 복잡도와 공간 복잡도

1. 시간복잡도와 공간 복잡도란? 시간 복잡도 - 시간 복잡도란 주어진 문제를 해결하기 위한 연산횟수를 말한다. 공간복잡도 - 알고리즘이나 프로그램이 실행되는 동안 사용하는 메모리의 공간의 크기를 의미한다. 2. 시간 복잡도 표기법 시간 복잡도는 아래와 같이 3가지의 표기법이 존재하지만 주로 사용되는 표기법은 빅-오(BigO-notation)표기법을 사용하여 표현한다. 왜냐면 수행 시간을 계산할 때 worst case를 기준으로 만족하는 수행 시간을 계산하기 위해서이다. 빅-오메가(best case) : 최선일 때의 연산 횟수를 나타낸 표기법 빅-세타(average case) : 보통일 때의 연산 횟수를 나타낸 표기법 빅-오 (worst case) : 최악일 때의 연산 횟수를 나타낸 표기법 알고리즘의 최..