C Programming C++

Data structure and algorithm

Data StructuresImage result for data structures and algorithms

  • A data structure is a logical method of representing data in memory.
  • Data structure is strictly described as an instance of an Abstract Data Type (ADT).
  • An Abstract Data Type is defined as a mathematical model of a user-defined type along with the operations performed on that model.
Data Structure Strengths Weaknesses
Array Fast access if index is known Slow search, fixed size
Stack Features last in – first out access Slow access to other elements
Queue Features first in – first out access Slow access to other elements
Linked list Quick insertion and deletion Slow search
Binary tree Quick insertion, deletion and search when tree is balanced Deletion procedure is complex
Hash table Fast insertion and access if key is known Inefficient memory usage, slow access if key is not known
Heap Fast insertion, deletion and access to largest element Slow access to other elements
Graph Simulates real world problems Some algorithms are slow and complex

An algorithm can be described as sequence of steps or instructions required to solve a given problem.

It is a finite set of instructions written to accomplish a particular task.

When designing an algorithm, one must ensure that the

algorithm adheres to the following criteria:

Input: Some input data (can be empty in some cases) externally supplied to the algorithm

Output: At least one output is produced

Finiteness: The algorithm must terminate after finite number of steps

Definiteness: The instructions must be clear and unambiguous

Effectiveness: Every instruction must be basic enough to be carried out on paper

Following are certain points to be considered

while writing an algorithm :

Representing an algorithm.

Designing an algorithm.

Analyzing an algorithm.

Algorithm Analysis

Algorithm Analysis involves comparing different algorithms written for a specific problem. All the algorithms are compared for their space and time complexities.

Space complexity: It refers to the amount of storage the algorithm consumes.

Time complexity: It is the time required by the algorithm for execution.

Following are the different types of time complexities:

Best-case time complexity: It is the measure of minimum time required for an algorithm to execute for a known input size.

Average case time complexity: Average time complexity is the measure of time an algorithm will require to execute, for a typical input data size. This method requires statistical calculations.

Worst-case time complexity: It is the measure of maximum time required for an algorithm to execute for a known input size.