솔

8.1 Lower Bounds for Searching Only by Comparisons of Keys 이 섹션에서는 키 비교만을 사용하여 배열에서 특정 키를 검색할 때 소모되는 최악의 경우 비교 횟수의 하한을 다룹니다.특히, Binary Search와 Sequential Search의 의사결정 트리(Decision Tree)를 사용하여 검색 과정의 효율성을 분석합니다. 의사결정 트리 (Decision Tree) • 정의:의사결정 트리는 키 를 배열에서 검색하는 과정에서 발생하는 모든 비교를 나타냅니다. • 각 내부 노드는 키 비교를 나타냅니다. • 각 리프 노드는 검색 결과를 나타냅니다 (성공적으로 검색된 위치 또는 실패). • 예시: • Figure 8.1: 정렬된 배열에서 이진 탐색(Binary ..

7.1 Computational Complexity 계산 복잡도란?  • **계산 복잡도(Computational Complexity)**는 특정 문제를 해결할 수 있는 모든 가능한 알고리즘의 효율성을 분석하는 학문이다. • 주로 다음 두 가지를 분석한다:  1. 시간 복잡도(Time Complexity): 알고리즘이 실행되는 데 필요한 시간. 2. 공간 복잡도(Space Complexity): 알고리즘이 사용하는 메모리 양. 여기서 중요한 것은 알고리즘을 개별적으로 분석하는 것이 아니라 문제 자체의 본질적인 복잡도를 분석한다는 점이다.예를 들어, 행렬 곱셈 문제에서는 최선의 알고리즘이라도 Θ(n²) 이상의 시간 복잡도를 가지며,이를 문제의 **하한(Lower Bound)**이라고 한다. 정렬 문제의 계..

큰 수의 곱셈을 분할해서 푸는문제.

1. Write an algorithm that finds the largest number in a list (an array) of n numbers.int fintLargest(std::vector& v){ int largest = v[0]; for(int i=1; i largest) largest = v[i]; }} 2. Write an algorithm that finds the m smallest numbers in a list of n numbers.std::vector findSmallThanM(std::vector& v, int m){ std::sort(v.begin(), v,end()); std::vector result(v.begin(), v.begin()+m); retur..