Could someone explain the difference between polynomial-time, non-polynomial-time, and exponential-time algorithms?
For example, if an algorithm takes O(n^2) time, then which category is it in?
ベストアンサー1
Below are some common Big-O functions while analyzing algorithms.
- O(1) - Constant time
- O(log(n)) - Logarithmic time
- O((log(n))c) - Polylogarithmic time
- O(n) - Linear time
- O(n log(n)) - Linearithmic time
- O(n2) - Quadratic time
- O(nc) - Polynomial time
- O(cn) - Exponential time
- O(n!) - Factorial time
(n = size of input, c = some constant)
Here is the model graph representing Big-O complexity of some functions
graph credits http://bigocheatsheet.com/