All about Data Structure & Algorithm (26) 썸네일형 리스트형 마스터 정리(Master Theorem) ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. ① 마스터 정리(master theorem)는 복잡한 알고리즘(recursive algorithm)의 시간 복잡도를 구하기 위해 사용한다. ② 마스터 정리로 해결할 수 있는 알고리즘의 구조는 다음과 같은 꼴을 따른다. ㉠ a>=1, b>1 인 상수여야 한다. ㉡ f(n)이 점근적으로 양수 함수값을 가지는 함수여야 한다. ㉢ 설명의 편의를 위해 A항 B항이라고 칭하겠다. ③ A항은 상위 문제를 해결하기 위해 상위 문제(super problem)를 하위 문제(sub problems)로 분할하는 데 소요되는 시간 복잡도이다. ㉠ 상수 a는 재귀 함수가 호출하는 하위 재귀 함수의 숫자이다. ㉡ 하위 재귀 함수는 n/b의 크기로 분할된다. ㉢ 상위 문제의 1.. 버블 정렬(Bubble sort)과 교환 정렬(Exchange sort) ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. ① 버블 정렬(bubble sort)과 교환 정렬은 O(N^2)의 시간 복잡도를 갖는 정렬 알고리즘 중 하나이다. ㉠ 정렬의 가장 이상적인 상황에서의 시간 복잡도는 O(N)이다. ⓐ 모든 항목이 정렬되어 있을 경우 단순 탐색만 진행하면 되기 때문에 O(N)의 시간 복잡도를 갖는다. ㉡ 버블 정렬과 교환 정렬의 최악의 상황에서 시간 복잡도는 O(N^2)이다. ② 버블 정렬과 교환정렬의 기본적인 작동원리는 인접한 두 수를 비교해 위치를 바꾸는 것으로 동일하다. ㉠ 버블 정렬의 작동 원리는 다음과 같다. ⓐ 선택된 배열의 첫 번째 요소와 두 번째 요소를 비교한다. 만약 정렬되어 있지 않다면 둘의 위치를 바꾼다. ⓑ 인접한 다음 쌍으로 이동하고 배열의 끝에.. 이전 1 2 3 4 다음
