Asymptotic Notation 편집하기

'''Asymptotic Notation''' is a mathematical tool used to describe the limiting behavior of an algorithm's complexity as the input size approaches infinity. It provides a way to analyze and compare algorithm efficiency by focusing on the growth rate of time or space complexity.
==Key Asymptotic Notations==
Asymptotic notation expresses how an algorithm's performance scales with input size. The most common types are:
===Big O Notation (O)===
*'''Definition:''' Represents an upper bound on an algorithm’s growth rate (worst-case complexity).
*'''Example:''' If an algorithm has O(n²) complexity, its runtime does not exceed a constant multiple of n² for large n.
*'''Usage:''' Ensures an algorithm will not perform worse than the given bound.
===Big Omega Notation (Ω)===
*'''Definition:''' Represents a lower bound on an algorithm’s growth rate (best-case complexity).
*'''Example:''' If an algorithm has Ω(n log n) complexity, its runtime is at least proportional to n log n.
*'''Usage:''' Guarantees that an algorithm will take at least the given time.
===Big Theta Notation (Θ)===
*'''Definition:''' Represents a tight bound (both upper and lower) on an algorithm’s growth rate.
*'''Example:''' If an algorithm has Θ(n log n) complexity, its runtime grows at exactly that rate.
*'''Usage:''' Defines an algorithm’s precise asymptotic behavior.
===Little o Notation (o)===
*'''Definition:''' Represents an upper bound that is not tight (strictly smaller growth rate).
*'''Example:''' If an algorithm has o(n²) complexity, its runtime grows slower than n² but not necessarily at a fixed rate.
===Little Omega Notation (ω)===
*'''Definition:''' Represents a lower bound that is not tight (strictly greater growth rate).
*'''Example:''' If an algorithm has ω(n log n) complexity, its runtime grows faster than n log n.
==Comparison of Notations==
{| class="wikitable"
!Notation!!Description!!Example Meaning
|-
|O(f(n))||Upper bound (worst-case)||O(n²) means runtime is at most proportional to n².
|-
|Ω(f(n))||Lower bound (best-case)||Ω(n log n) means runtime is at least proportional to n log n.
|-
|Θ(f(n))||Tight bound||Θ(n log n) means runtime is both at most and at least proportional to n log n.
|-
|o(f(n))||Strictly smaller upper bound||o(n²) means runtime grows slower than n².
|-
|ω(f(n))||Strictly greater lower bound||ω(n log n) means runtime grows faster than n log n.
|}
==Examples==
*'''Linear Search'''
**Complexity: O(n) (worst case), Ω(1) (best case).
*'''Binary Search'''
**Complexity: O(log n), Ω(1).
*'''Merge Sort'''
**Complexity: O(n log n), Θ(n log n).
==Applications==
Asymptotic notation is widely used in:
*'''Algorithm Analysis:''' Comparing different algorithms based on efficiency.
*'''Data Structures:''' Evaluating operations such as searching, insertion, and deletion.
*'''Computational Complexity Theory:''' Classifying problems into P, NP, NP-complete, etc.
==See Also==
*[[Big O Notation]]
*[[Computational Complexity]]
*[[Time Complexity]]
*[[Space Complexity]]
*[[Algorithm Complexity]]
*[[Master Theorem]]
[[Category:Algorithm]]