|
Complexity
|
Running Time
|
Description
|
|
constant
|
O(1)
|
It takes a constant number of steps for
performing a given operation (for example 1, 5, 10 or other number) and this count does not depend on the size of the input data. |
|
logarithmic
|
O(log(N))
|
It takes the order of log(N) steps, where
the base of the logarithm is most often 2, for performing a given operation on N elements. For example, if N = 1,000,000, an algorithm with a complexity O(log(N)) would do about 20 steps (with a constant precision). Since the base of the logarithm is not of a vital importance for the order of the operation count, it is usually omitted. |
|
linear
|
O(N)
|
It takes nearly the same amount of
steps as the number of elements for performing an operation on N elements. For example, if we have 1,000 elements, it takes about 1,000 steps. Linear complexity means that the number of elements and the number of steps are linearly dependent, for example the number of steps for N elements can be N/2 or 3*N. |
|
|
O(n*log(n))
|
It takes N*log(N) steps for performing a
given operation on N elements. For example, if you have 1,000 elements, it will take about 10,000 steps. |
|
quadratic
|
O(n2)
|
It takes the order of N2 number
of steps,
where the N is the size of the input data, for performing a given operation. For example if N = 100, it takes about 10,000 steps. Actually we have a quadratic complexity when the number of steps is in quadratic relation with the size of the input data. For example for N elements the steps can be of the order of 3*N 2/2. |
|
cubic
|
O(n3)
|
It takes the order of N3 steps,
where N is
the size of the input data, for performing an operation on N elements. For example, if we have 100 elements, it takes about 1,000,000 steps |
|
exponential
|
O(2n), O(N!),
O(nk), … |
It takes a number of steps, which is with
an exponential dependability with the size of the input data, to perform an operation on N elements. For example, if N = 10, the exponential function 2N has a value of 1024, if N = 20, it has a value of 1 048 576, and if N = 100, it has a value of a number with about 30 digits. The exponential function N! grows even faster: for N = 5 it has a value of 120, for N = 10 it has a value of 3,628,800 and for N = 20 – 2,432,90,008,176,640,000 |
Complexity and Execution Timewith 50,000,000 elementary operations per second
\
|
Algorithm
|
10
|
20
|
50
|
100
|
1000
|
10000
|
100000
|
|
O(1)
|
< 1 sec.
|
< 1 sec.
|
< 1 sec.
|
< 1 sec.
|
< 1 sec.
|
< 1 sec.
|
< 1 sec.
|
|
O(log(n))
|
< 1 sec.
|
< 1 sec.
|
< 1 sec.
|
< 1 sec.
|
< 1 sec.
|
< 1 sec.
|
< 1 sec.
|
|
O(n)
|
< 1 sec.
|
< 1 sec.
|
< 1 sec.
|
< 1 sec.
|
< 1 sec.
|
< 1 sec.
|
< 1 sec.
|
|
O(n*log(n))
|
< 1 sec.
|
< 1 sec.
|
< 1 sec.
|
< 1 sec.
|
< 1 sec.
|
< 1 sec.
|
< 1 sec.
|
|
O(n2)
|
< 1 sec.
|
< 1 sec.
|
< 1 sec.
|
< 1 sec.
|
< 1 sec.
|
2 sec.
|
3-4 min.
|
|
O(n3)
|
< 1 sec.
|
< 1 sec.
|
< 1 sec.
|
< 1 sec.
|
20 sec.
|
5.55 hours.
|
231.5 days
|
|
O(2n)
|
< 1 sec.
|
< 1 sec.
|
260 days
|
hangs
|
hangs
|
hangs
|
hangs
|
|
O(n!)
|
< 1 sec.
|
hangs
|
hangs
|
hangs
|
hangs
|
hangs
|
hangs
|
|
O(nn)
|
3-4 mín.
|
hangs
|
hangs
|
hangs
|
hangs
|
hangs
|
hangs
|
Comparison between Basic Data Structures
|
Data structure
|
Addition
|
Search
|
Deletion
|
Access
|
|
Array (T[])
|
O(N)
|
O(N)
|
O(N)
|
O(1)
|
|
Linked list (LinkedList<T>)
|
O(1)
|
O(N)
|
O(N)
|
O(N)
|
|
Dynamic array (List<T>)
|
O(1)
|
O(N)
|
O(N)
|
O(1)
|
|
Stack (Stack<T>)
|
O(1)
|
-
|
O(1)
|
-
|
|
Queue (Queue<T>)
|
O(1)
|
-
|
O(1)
|
-
|
|
Dictionary, implemented with a hash-table (Dictionary<K,
T>)
|
O(1)
|
O(1)
|
O(1)
|
-
|
|
Dictionary, implemented with a balanced search tree (SortedDictionary<K,
T>)
|
O(log(N))
|
O(log(N))
|
O(log(N))
|
-
|
|
Set, implemented with a hash-table (HashSet<T>)
|
O(1)
|
O(1)
|
O(1)
|
-
|
|
set, implemented with a balanced search tree (SortedSet<T>)
|
O(log(N))
|
O(log(N))
|
O(log(N))
|
-
|
0 nhận xét:
Đăng nhận xét