Master Theorem 편집하기

'''Master Theorem''' is a formula used to analyze the time complexity of recursive algorithms, particularly divide-and-conquer algorithms. It provides a direct way to determine asymptotic complexity without requiring iterative expansion or recurrence tree analysis.
==Master Theorem Formula==
A recurrence of the form:
*T(n) = aT(n/b) + O(n^d)
where:
*'''a''' = number of recursive calls,
*'''b''' = factor by which the problem size is reduced in each recursion,
*'''O(n^d)''' = cost of work done outside the recursive calls,
can be solved using the Master Theorem by comparing d with log_b(a):
{| class="wikitable"
!Case!!Condition!!Complexity
|-
|Case 1||d > log_b(a)||O(n^d)
|-
|Case 2||d = log_b(a)||O(n^d log n)
|-
|Case 3||d < log_b(a)||O(n^(log_b(a)))
|}
==Examples==
*'''Merge Sort'''
**Recurrence: T(n) = 2T(n/2) + O(n)
**a = 2, b = 2, d = 1
**log_2(2) = 1 → d = log_b(a)
**Case 2 applies → Complexity: O(n log n)

*'''Binary Search'''
**Recurrence: T(n) = T(n/2) + O(1)
**a = 1, b = 2, d = 0
**log_2(1) = 0 → d = log_b(a)
**Case 2 applies → Complexity: O(log n)

*'''Strassen’s Matrix Multiplication'''
**Recurrence: T(n) = 7T(n/2) + O(n²)
**a = 7, b = 2, d = 2
**log_2(7) ≈ 2.81 → d < log_b(a)
**Case 3 applies → Complexity: O(n^2.81)
==Limitations==
*Only applicable for recurrences that match the form T(n) = aT(n/b) + O(n^d).
*Does not work well for irregular or non-uniform recurrence relations.
==Applications==
*'''Divide-and-Conquer Algorithms:''' Merge Sort, Quick Sort, Binary Search.
*'''Matrix Multiplication:''' Strassen’s Algorithm.
*'''Computational Complexity Analysis:''' Used in algorithm design and performance evaluation.
==See Also==
*[[Divide-and-Conquer Algorithm]]
*[[Algorithm Complexity]]
*[[Asymptotic Notation]]
*[[Recurrence Relation]]
*[[Big O Notation]]
[[Category:Algorithm]]