Classification of Algorithms
#computer-science #algorithms #classification-of-algorithms
Algorithm Definition
A set of instructions required to complete a given task.
For any given problem, there will be multiple algorithms (for example,
Dijkstra's Shortest Path Algorithm is one shortest path algorithm).
Ideally, you want to use the most efficient algorithm -- i.e. the one which
runs quickly and uses minimal resources.
Time Complexity
How long does the algorithm take to run compared to other algorithms.
Space Complexity
How much memory is required compared with other algorithms.
The key factor is called the input size or the problem size . Typically, this
is the number of data items/nodes/etc.
Algorithm Efficiency Based on Problem Size
Some algorithms are effective for small data sets, but inefficient for
large ones.
Short Overview of Mathematical Functions
, Key Functions:
Constant functions 49
Linear functions 2x
Polynomial functions 2x 2
Exponential functions 2 x
Logarithmic functions log 10
x
Definition of a Permutation
A permutation is the number of ways a set of n items can be arranged.
In the trivial case, this is n!
Big O Notation
Describes the time complexity of an algorithm in the worse-case
scenario [1] as the input time increases.
For example, the bubble sort becomes rapidly unusable, while the
mergesort continues to work in a reasonable amount of time.
Big O calculates the maximum time for an algorithm to complete given n
data items.
Five Main Big O Notations
Constant Time O(1): The algorithm takes the same amount of time
however big the input size is
Logarithmic Time O(log n): The algorithm scales with log n
Linear Time O(n): Time is directly proportional to the size of the
data
Polynomial Time O(n 2
)
Exponential Time O(2 n
)
Disambiguation
#computer-science #algorithms #classification-of-algorithms
Algorithm Definition
A set of instructions required to complete a given task.
For any given problem, there will be multiple algorithms (for example,
Dijkstra's Shortest Path Algorithm is one shortest path algorithm).
Ideally, you want to use the most efficient algorithm -- i.e. the one which
runs quickly and uses minimal resources.
Time Complexity
How long does the algorithm take to run compared to other algorithms.
Space Complexity
How much memory is required compared with other algorithms.
The key factor is called the input size or the problem size . Typically, this
is the number of data items/nodes/etc.
Algorithm Efficiency Based on Problem Size
Some algorithms are effective for small data sets, but inefficient for
large ones.
Short Overview of Mathematical Functions
, Key Functions:
Constant functions 49
Linear functions 2x
Polynomial functions 2x 2
Exponential functions 2 x
Logarithmic functions log 10
x
Definition of a Permutation
A permutation is the number of ways a set of n items can be arranged.
In the trivial case, this is n!
Big O Notation
Describes the time complexity of an algorithm in the worse-case
scenario [1] as the input time increases.
For example, the bubble sort becomes rapidly unusable, while the
mergesort continues to work in a reasonable amount of time.
Big O calculates the maximum time for an algorithm to complete given n
data items.
Five Main Big O Notations
Constant Time O(1): The algorithm takes the same amount of time
however big the input size is
Logarithmic Time O(log n): The algorithm scales with log n
Linear Time O(n): Time is directly proportional to the size of the
data
Polynomial Time O(n 2
)
Exponential Time O(2 n
)
Disambiguation
