7. 자료구조 - 자료구조의 개념

(171)

연산 시간 그룹

상수시간: O(1) * 데이터양에 관계없이 일정	로그시간: O(logn)	선형시간: O(n)	n로그시간: O(nlogn)
평방시간: O(n²)	입방시간: O(n³)	지수시간: O(2ⁿ)	계승시간: O(n!)

 

접근적 표기법 = 근사(대략적) 표기법

빅오(Big-oh) 표기법	n ≥ n₀를 만족하는 모든 n에 대하여 f(n) ≤ c⋅g(n)인 조건을 만족하는 2개의 양의 상수 c와 n₀가 존재하기만 하면 f(n) = O(g(n))이다.
오메가(Omega)표기법	n ≥ n₀를 만족하는 모든 n에 대하여 f(n) ≥ c⋅g(n)인 조건을 만족하는 2개의 양의 상수 c와 n₀가 존재하기만 하면 f(n) = ≥ Ω(g(n))이다.

 

순환(recursion) = 재귀호출 = 되부름

- 실행 중인 함수가 자기 자신을 되부름 호출하는 형태

- 때때로 다른 어떤 방법으로는 풀기 어려운 문제에 대하여 간단하면서도 세련된 해결책을 만드는데 사용

- 분할 정복의 특성을 가진 문제가 가장 적합

- 일반적으로 반복문으로 대체 가능, 반복은 표현이 더 길 수 있음

- 순환이 일어날 떄마다 새로운 활성화 레코드가 만들어짐 -> 시간 복잡도, 공간 복잡도 커짐

- 피보나치 수열 등

lib(n)

    if(n ≤ 0) then return 0;

    else if (n = 1) then return 1l

    else return (lib(n - 1) + lib(n - 2));

end lib()