복잡도2 Python 자료구조 & 알고리즘 - 재귀호출 1. 재귀호출(recusive call) 함수 안에서 동일한 함수를 호출하는 형태 여러 알고리즘, 고급 정렬 알고히즘 작성시 자주 사용됨 1-1. 재귀 호출 분석 2! = 1 * 2 3! = 1 * 2 * 3 4! = 1 * 2 * 3 * 4 = 3! * 4 1-2. 규칙 n! = n * (n-1)! 함수로 만들어 보자 함수(n)은 n=1 함수(n)은 n>1 이면 return n*함수(n-1) 1-3. 검증 2! 함수(2)이면 2>1 이므로 2 * 함수(1) 함수(1)은 1이므로 return 2 * 1, 답은 2 3! 함수(3)이면 3>1 이므로 3 * 함수(2) 함수(2)는 위 계산에 의해 2! 이므로 return 2*1 = 2 3 * 함수(2) = 3 * 2 = 3 * 2 * 1, 답은 6 4! 함수.. 2023. 2. 21. Python 자료구조 & 알고리즘 - 복잡도 1. 알고리즘 복잡도 표현방법 1-1. 알고리즘 복잡도 계산이 필요한 이유 하나의 문제를 푸는 알고리즘은 다양함 * 정수의 절대값을 구하는 방법 * 방법1 : 값이 음수인지 확인해서 0보다 작은 음수일 때 -1을 곱하기 * 방법2 : 정수값을 재곱한 값에 루트를 씌우기 디양한 알고리즘 중 어떤 알고리즘이 더 좋은지 분석하기 위해 복잡도를 정의하고 계산함 1-2. 알고리즘 복잡도 계산 항목 공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈 시간 복잡도 : 알고리즘 실행 속도 1-3. 알고리즘 성능 표기법 오메가 표기법 알고리즘 최상의 실행 시간을 표기 세타 표기법 알고리즘 평균 실행시간을 표기 빅오 표기법 최악의 실행 시간을 표기 아무리 최악의 상황이라도 이 정도의 성능은 보장함을 의미 가장 많이 사용 1.. 2023. 2. 20. 이전 1 다음
