자료구조, 알고리즘 썸네일형 리스트형 [자료구조] 재귀 재귀(Recursion) : 자신을 정의할 때 자기 자신을 재참조 하는 것. 즉, 재귀 함수 : 함수 내에서 자기 자신을 다시 호출하는 함수. 어려운 문제를 단순화하는 데에 종종 사용된다. Q. 완료되지 않은 함수를 다시 호출하는 것이 가능한가? A. 함수 실행 중 다시 해당 함수가 호출될 시, 해당 함수의 복사본이 하나 더 만들어져서 복사본이 실행된다. 따라서 가능하다. 재귀 함수가 활용되는 대표적인 예시 - 팩토리얼, 피보나치 수열, 하노이 타워 더보기 [자료구조] 알고리즘의 성능평가와 ADT 공간 복잡도(Space Complexity) : 알고리즘의 메모리 사용량을 평가하기 위한 척도. 시간 복잡도(Time Complexity) : 알고리즘의 수행속도를 평가하기 위한 척도. 데이터 수의 증가에 따른 연산횟수의 변화 정도를 판단할 수 있다. 최악의 경우를 기준으로 핵심 연산의 횟수를 계산한다. 일반적으로 '빅-오 표기법'을 이용한다. 빅-오 표기법(Big-Oh Notation) 데이터 수의 증가에 따른 연산횟수 증가율의 상한선을 표현하는 표기법이다. ▶증명 : "두 개의 함수 f(n)과 g(n)이 주어졌을 때, 모든 n≥K에 대하여 f(n)≤Cg(n)을 만족하는 두 개의 상수 C, K가 존재하면, f(n)의 빅-오는 O(g(n))이다." 대표적인 빅-오 표기들의 성능 비교(오른쪽으로 갈 수록 .. 더보기 이전 1 다음