Algorithms (알고리즘)/Sorting (정렬)1 Comparison Model 에서의 정렬 알고리즘의 시간복잡도 [주의] 이번 주제는 좀 더 수학적인 증명이 가미되어 있습니다. 이번 시간의 주제는 과연 정렬 알고리즘의 Worst Case 시간 복잡도 (Time Complexity) 의 Lower Bound 에 대한 수학적 증명입니다. 이 때, 이번 주제에서 정렬 알고리즘의 경우 Comparison Model, 즉 "임의의 배열 A 내에서 임의의 두 Element 들을 선택해 상수 시간 (Constant Time) 내에 두 element 값의 비교 (Comparsion) 를 통해 한 쪽이 다른 element 에 비해 작거나 크다는걸 결정할 수 있다" 를 전제하고 있습니다. 조금 더 디테일한 전제조건들은 다음과 같습니다. 1. 서로 다른 두 원소들간의 상대적인 순서를 값의 비교를 통해 결정한다 2. 서로 다른 임의의 .. 2022. 8. 5. 이전 1 다음
