You may wonder why we pay so much attention to data structures and why we review them in such a great details. The reason is that, without knowing the basic data structures and computer algorithms in programming well, you cannot be good developers. Whoever knows data structures and algorithms well and starts thinking about their correct use has big chance to become a professional – one that analyzes the problems in depth and proposes efficient solutions.
Data structures are a specific way of organizing data in a specialized format on a computer so that the information can be organized, processed, stored, and retrieved quickly and effectively. They are a means of handling information, rendering the data for easy use. Data structures are the core building blocks of algorithms and real-life applications. Every application, piece of software, or programs foundation consists of two components: algorithms and data. Data is information, and algorithms are rules and instructions that turn the data into something useful to programming.
There are various types of data structures and they represent several ways to organize data in memory to perform several operations efficiently. We use it to manage, process, and get relevant information in an efficient manner. There will be two primary components in every data structure: data and various operations working on that data. Data is information, and operations are algorithms working on that data to get valuable insights.
Points to note
Related data + Permissible operations on the data = Data Structures
Data structures + Algorithms = Programs
Operations on any data structure can be grouped into two categories: Query Operations and Modification Operations. These operations are frequent in real-life applications, and we should study the design, code, and analysis of critical operations for each data structure. We may include additional operations for data structures based on requirements of applications.
- Query operations: These operations will return some information about the data structure S. For example, search(S, k), findMax(S), findMin(S), findSuccessor(S, x), etc., are the query operations on a data structure.
- Modification operations: These operations will update or change the data structure S. For example, insert(S, x), delete(S, x), sort(D), etc., are modification operations on a data structure.
Different data structures take different times to execute various operations. So we compare the efficiency of operations provided by multiple data structures and choose a correct data structure among them to improve our code performance.
Algorithmic complexity is a measure of how long an algorithm would take to complete given an input of size n. If an algorithm has to scale, it should compute the result within a finite and practical time bound even for large values of n. For this reason, complexity is calculated asymptotically as n approaches infinity. While complexity is usually in terms of time, sometimes complexity is also analyzed in terms of space, which translates to the algorithm's memory requirements. Analysis of an algorithm's complexity is helpful when comparing algorithms or seeking improvements.
Algorithm complexity evaluates the order of the count of operations, performed by a given or algorithm as a function of the size of the input data. To put this simpler, complexity is a rough approximation of the number of steps necessary to execute an algorithm. When we evaluate complexity we speak of order of operation count, not of their exact count. For example if we have an order of N2 operations to process N elements, then N2/2 and 3*N2 are of one and the same quadratic order.
Algorithm complexity is commonly represented with the O(f) notation, also known as asymptotic notation or “Big O notation”, where f is the function of the size of the input data. The asymptotic computational complexity O(f) measures the order of the consumed resources (CPU time, memory, etc.) by certain algorithm expressed as function of the input data size.
Complexity can be constant, logarithmic, linear, n*log(n), quadratic, cubic, exponential, etc. This is respectively the order of constant, logarithmic, linear and so on, number of steps, are executed to solve a given problem. For simplicity, sometime instead of “algorithms complexity” or just “complexity” we use the term “running time”.
| 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*N2/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. |
References:
No comments:
Post a Comment