점근석 분석점근적 분석은 함수의 인자가 특정 값이나 무한대로 접근할 때의 함수의 행동을 설명하는 수학적 방법이다.컴퓨터 공학에서는 알고리즘을 실행 시간이나 공간 사용량이 입력 크기에 따라 어떻게 증가하는지를 기준으로 분류한다. => 시간복잡도, 공간복잡도 계산에 활용할 수 있다. 빅오 표기법(Big O notation)간단히 말해, 빅오는 어떤 함수 f(x)의 성장률이 다른 함수 g(x)의 성장률에 비해 같거나 느리다는 것을 의미한다.빅오 외에도 빅세타, 빅오메가가 있으나 빅오를 사용하는 이유는 알고리즘 설계 시 최악 복잡도를 고려해야 하기 때문이다.최악의 경우 = 즉 어느 상한선까지 같거나 그 이하로 증가하는지를 알아야 한다. 빅 오(O): f(x)의 성장률이 g(x)에 비례하여 증가하거나 그 이..
전위순회 후위순회 중위순회 결정트리(Decision Tree) internal node: 질문지 external node: 선택지 완전이진트리의 특징 모든 Internal Node(자식)의 수가 2일 때 external node의 수 = internal node의 수 +1 총 노드 수 = 2 * external node의 수 - 1 height ≤ internal node의 수 (left or right node로만 이루어진 트리일 때 가장 큼) height ≤ (총 노드 수 - 1) / 2 external node의 수 ≤ 2^height height ≥ log2e h ≥ log2(n+1) - 1 ⇒ 시간 복잡도 하한 O(logn)) 이진탐색트리 중위 순회를 사용하면, 오름차순으로 데이터 visit 가..
트리 계층 구조를 갖는 자료구조 부모 노드 - 자식 노드의 관계 트리의 용어 Root : 위치 상 맨 위 노드. 즉, 부모가 없는 노드. Internal node : 내부 노드. 자식이 적어도 하나 이상 있는 노드 External node(=Leaf) : 위치상 맨 끝 노드 Ancestors : 한 노드의 모든 상위 노드. 직속 상위+ root 까지의 모든 상위노드 Descendants : 한 노드의 모든 하위노드. 직속 하위 + leaf 까지의 모든 하위노드 Depth(깊이) : 한 노드의 조상 수. root = 0부터 시작해서 아래로 갈수록 1씩 늘어남. Height(높이) : 트리의 노드 중 Depth(0~)의 최댓값 Subtree(부분트리) : 한 노드와 그 노드의 후손을 전부 포함하는 트리 요소..
