What are Searching Algorithms?
Searching Algorithms are designed to check for an element or retrieve an element from any data structure where it is stored. Based on the type of search operation, these algorithms are generally classified into two categories:
Sequential search - the list or array is traversed sequentially and every element is checked. For example, linear search.
Interval search - These algorithms are specifically designed for searching in already-sorted data structures. These types of searching algorithms are much more efficient than sequential search algorithms as they target the center of the structure and divide the search space in half. For example, binary search.
What is a brute force algorithm?
The brute force algorithm is an example of sequential search algorithms. The brute force method for finding an item in a table ideally checks all entries of the table sequentially.
Brute Force Algorithms are straightforward methods of solving a problem that relies on just computing power and involve the trying of every possibility rather than advanced techniques to improve efficiency.
Features of the Brute Force Algorithm
Brute force algorithms have no preprocessing phase. Data preprocessing includes cleaning, normalisation, transformation, feature extraction, instance selection, and selection, etc. The result of data preprocessing is the final training set. It may affect the way in which outcomes of the final data processing can be interpreted.
These algorithms also constantly require extra storage space. This is due to the processing of all possibilities and storing them for referencing. The algorithm also shifts the window by exactly 1 position to the right. “Shifting the window” is a technique known as a sliding window, used in the brute force algorithm. A sliding window is a sub-list that runs over an underlying collection.
In a brute force algorithm, the comparison of values can be done in any order. Some algorithms have a particular way of comparing values, either by consecutive indices or ascending/descending values, but the brute force algorithm has no such order.
The time complexity of the searching phase in a brute force algorithm is O(m*n) or is also written as O(nm). So, if we were to search for a string of "n" characters in a string of "m" characters using the brute force algorithm, it would take us n*m tries. In fact, the running time is actually O(m(n-m)), but since the Big-O notation is an upper bound, this can also be written as O(nm) as mn ≥ m(n-m). With a string of “n” characters, we can expect 2n text character comparisons.
Article was written for CyberClubNPSi
Comments