Hello Friends, Lets discuss
about the data structure.
Let’s elaborate the data
structure as data + structure - > structure of data
Data Structure is a particular way of storing
and organizing data so that it can be used efficiently
In other word a data structure is a special
format for organizing and storing data.
How data is stored in a
structure?
Why a structure is required
for the data?
What are the features of
structure for the data?
Think about above questions
when we have a very limited amount of data then structure is not a concern but
when the size increases than operation on data majorly impacted. That’s why
whenever we are storing data we need to define the structure of data so that we
can easily traverse, search and update the data. The use case of the data
decide that which data structure should be used.
Type of data
structure
1)
Linear data structure
2)
Non – linear data structure
Linear data
Structure
In linear data structure
elements are accessed in sequential order but it’s not compulsory to store all
elements sequentially.
Type of linear
data structure
1)
Arrays
2)
Linked List
3)
Stacks
4)
Queue
Non-linear data
structure –
In non-linear data structure
element are accessed and stored in non-linear order
Type of
non-linear data structure
1)
Trees
2)
Graphs
Data structure operations -
data structure are processed by means of certain operations. In fact operations
decide the selection of data structure, for example for frequent insertion and
deletion we prefer to use Linked List similarly for fast iteration we will
choose arrays.
The following operations play
major role in data structure.
1)
Traversing
2)
Searching
3)
Insertion
4)
Deletion
5)
Sorting
6)
Merging
Before jumping to the
complexity lets discuss about Asymptotic Notation
Asymptotic Notation
Asymptotic Notations are
languages that allow us to analyze an algorithm’s running time by identifying
its behavior as the input size for the algorithm increases. This is also known
as an algorithm’s growth rate.
1)
Big-O Notation
2)
Omega- Ω
Notation
3)
Theta Θ Notation
Big-O Notation
This notation gives the tight
upper bound of the given function. It is represented as
f (n) =O (g (n))
Omega- Ω Notation
This notation gives the
tighter lower bound of the given algorithm. It is represented as
f (n) = Ω
(g(n))
Theta Θ Notation
This notation decides whether
the upper and lower bounds of a given function are same. It is represented as
f (n) = Θ
(g(n))
Time Complexity –
The complexity of an
algorithm is a function describing the efficiency of the algorithm in terms of
the amount of data processed by algorithm. There are two main complexity
measures of the efficiency of an algorithm:
Time complexity – is a function describing the amount of time taken
by an algorithm. For example if we want to search an element in an Array then
we have traverse a compare n element. If element found at 0th index
than complexity will be O (1), if element found at nth index than time
complexity will be O (n).
Space complexity - is a function describing the amount of memory
(space) taken by an algorithm.
Here I have added the
complexity of different data structures.
|
Data Structure
|
Time Complexity
|
|||||||
|
Average
|
Worst
|
|||||||
|
Access
|
Search
|
Insertion
|
Deletion
|
Access
|
Search
|
Insertion
|
Deletion
|
|
|
Θ(1)
|
Θ(n)
|
Θ(n)
|
Θ(n)
|
O(1)
|
O(n)
|
O(n)
|
O(n)
|
|
|
Θ(n)
|
Θ(n)
|
Θ(1)
|
Θ(1)
|
O(n)
|
O(n)
|
O(1)
|
O(1)
|
|
|
Θ(n)
|
Θ(n)
|
Θ(1)
|
Θ(1)
|
O(n)
|
O(n)
|
O(1)
|
O(1)
|
|
|
Θ(n)
|
Θ(n)
|
Θ(1)
|
Θ(1)
|
O(n)
|
O(n)
|
O(1)
|
O(1)
|
|
|
Θ(n)
|
Θ(n)
|
Θ(1)
|
Θ(1)
|
O(n)
|
O(n)
|
O(1)
|
O(1)
|
|
|
Θ(log(n))
|
Θ(log(n))
|
Θ(log(n))
|
Θ(log(n))
|
O(n)
|
O(n)
|
O(n)
|
O(n)
|
|
|
N/A
|
Θ(1)
|
Θ(1)
|
Θ(1)
|
N/A
|
O(n)
|
O(n)
|
O(n)
|
|
|
Θ(log(n))
|
Θ(log(n))
|
Θ(log(n))
|
Θ(log(n))
|
O(n)
|
O(n)
|
O(n)
|
O(n)
|
|
|
N/A
|
Θ(log(n))
|
Θ(log(n))
|
Θ(log(n))
|
N/A
|
O(n)
|
O(n)
|
O(n)
|
|
|
Θ(log(n))
|
Θ(log(n))
|
Θ(log(n))
|
Θ(log(n))
|
O(log(n))
|
O(log(n))
|
O(log(n))
|
O(log(n))
|
|
|
Θ(log(n))
|
Θ(log(n))
|
Θ(log(n))
|
Θ(log(n))
|
O(log(n))
|
O(log(n))
|
O(log(n))
|
O(log(n))
|
|
|
N/A
|
Θ(log(n))
|
Θ(log(n))
|
Θ(log(n))
|
N/A
|
O(log(n))
|
O(log(n))
|
O(log(n))
|
|
|
Θ(log(n))
|
Θ(log(n))
|
Θ(log(n))
|
Θ(log(n))
|
O(log(n))
|
O(log(n))
|
O(log(n))
|
O(log(n))
|
|
|
Θ(log(n))
|
Θ(log(n))
|
Θ(log(n))
|
Θ(log(n))
|
O(n)
|
O(n)
|
O(n)
|
O(n)
|
|
Time complexity of different
sorting algorithms
|
Algorithm
|
Time Complexity
|
||
|
Best
|
Average
|
Worst
|
|
|
Ω(n log(n))
|
Θ(n log(n))
|
O(n^2)
|
|
|
Ω(n log(n))
|
Θ(n log(n))
|
O(n log(n))
|
|
|
Ω(n)
|
Θ(n log(n))
|
O(n log(n))
|
|
|
Ω(n log(n))
|
Θ(n log(n))
|
O(n log(n))
|
|
|
Ω(n)
|
Θ(n^2)
|
O(n^2)
|
|
|
Ω(n)
|
Θ(n^2)
|
O(n^2)
|
|
|
Ω(n^2)
|
Θ(n^2)
|
O(n^2)
|
|
|
Ω(n log(n))
|
Θ(n log(n))
|
O(n^2)
|
|
|
Ω(n log(n))
|
Θ(n(log(n))^2)
|
O(n(log(n))^2)
|
|
|
Ω(n+k)
|
Θ(n+k)
|
O(n^2)
|
|
|
Ω(nk)
|
Θ(nk)
|
O(nk)
|
|
|
Ω(n+k)
|
Θ(n+k)
|
O(n+k)
|
|
|
Ω(n)
|
Θ(n log(n))
|
O(n log(n))
|
|
Nice information, very usefull thanks
ReplyDelete