Algorithm Complexity
IT 위키
Algorithm Complexity is a measure of the efficiency of an algorithm in terms of time and space usage as the input size grows. It helps in comparing different algorithms and understanding their performance characteristics.
1 Key Concepts[편집 | 원본 편집]
- Time Complexity: Measures the amount of time an algorithm takes to complete as a function of input size.
- Space Complexity: Measures the amount of memory an algorithm requires during execution.
- Asymptotic Notation: Describes the growth rate of complexity functions, ignoring constant factors.
2 Time Complexity[편집 | 원본 편집]
Time complexity is classified based on how the runtime increases with input size:
| Complexity | Notation | Description | Example |
|---|---|---|---|
| Constant | O(1) | Execution time is independent of input size. | Accessing an array element. |
| Logarithmic | O(log n) | Execution time increases logarithmically. | Binary search. |
| Linear | O(n) | Execution time grows proportionally to input size. | Iterating through an array. |
| Linearithmic | O(n log n) | Grows slightly faster than linear. | Merge Sort, Quick Sort (average case). |
| Quadratic | O(n²) | Execution time grows quadratically. | Bubble Sort, Insertion Sort. |
| Exponential | O(2ⁿ) | Grows exponentially with input size. | Solving the traveling salesman problem using brute force. |
3 Space Complexity[편집 | 원본 편집]
Space complexity considers both:
- Auxiliary Space: Extra memory used by the algorithm beyond input storage.
- Recursive Stack Space: Memory consumed by recursive function calls.
| Algorithm | Space Complexity | Description |
|---|---|---|
| Merge Sort | O(n) | Requires additional space for merging. |
| Quick Sort | O(log n) | Uses recursive stack space. |
| Bubble Sort | O(1) | Uses minimal extra memory. |
4 Best, Worst, and Average Case Complexity[편집 | 원본 편집]
An algorithm’s complexity can be analyzed in different scenarios:
- Best Case: The input requires the fewest steps (e.g., sorted input in insertion sort).
- Worst Case: The input requires the maximum number of steps (e.g., reversed input in insertion sort).
- Average Case: The expected runtime over all possible inputs.
5 Complexity Classes[편집 | 원본 편집]
Computational complexity theory categorizes problems into different classes:
| Complexity Class | Description | Example Problems |
|---|---|---|
| P | Problems solvable in polynomial time. | Sorting, shortest path. |
| NP | Problems verifiable in polynomial time. | Traveling Salesman, Boolean Satisfiability (SAT). |
| NP-complete | Hardest problems in NP; if one is solved in polynomial time, all NP problems can be solved in polynomial time. | 3-SAT, Hamiltonian Cycle. |
| NP-hard | At least as hard as NP-complete problems but not necessarily in NP. | Halting Problem, Generalized TSP. |
6 Practical Considerations[편집 | 원본 편집]
- Trade-offs: Algorithms with lower time complexity may use more space and vice versa.
- Optimization: Some problems allow for better solutions through heuristics or approximation.
- Parallelization: Some algorithms can be optimized using parallel computing.
