DEV Community

loading...

Basic Algorithms

vrnsky profile image Yegor Voronyansky ・3 min read

Basic termins of the algorithms

Algorithm call sequence of the step by executing their getting some result.
For more detail information, look at the wiki Algorithm

The speed of algorithm execution meausure with big O notation. Which show how much increase count of operation with increasing input data.

Binary Search

Binary search. This algorithm designed for search element at the array. Before start searching we need to sort input data. If input data is not sorted algorithm is failed.
How we will find element - index of the search element

  1. Find middle element at the array: (middle=array.length-low)/2
  1. Compare element at array[middle] with search element and make things bottom.
  2. If array[middle] greater than search element, then move pointer middle to the high - 1
  3. If expression above is false make low = middle + 1
  4. While low <= high repeat steps 1-4

Selection sort

Effeciency - in worst case O(n^2)
This algorithm works by next way:

  1. Find index of minimum element at the array.
  2. Get value of which located at the founded index at step 1.
  3. Save value to the new array, which we accept as sorted.
  4. Remove from original array value which located at the founded index at step 1.
  5. While array is not empty repeat 1-4

Bubble sort

Efficiency O(n^2) (implementation use inner for loop)

  1. Make loop which started from zero index.
  2. Make another loop, which start from one index.
  3. Get element from array located at the outer and inner index counter of the loops. 4.Compare elements, and if needs, swap it.

Fast sorting

This algorithm uses at the java.lang.util.Collections.sort
Efficiency O(nlog(n))

  1. Choose any element which marked as basic element (best choose it is element at the middle).
  2. At the left of basic element collect all elements that smaller than basic element.
  3. At the right of basic element collect all elements that greater than basic element.
  4. Repeat step 1-3 until we don't have 1-length array.

Deepth search

This algorithm applicable for graph data structure. Take an graph of people's friends. For example, how to find at the your environment seller of the books.

  1. First check that we have not the book seller at the our friends or friends of friends
  2. If book seller detected at the step 1. Good!
  3. If book seller not found, let's go to deeper. Start search at the friends of friends of your friends.
  4. Repeat step 1-3 until we haven't result.

Greedy algorithm

This algorithm designed for the find acceptable solution, not ideal.
For example will take a load vehiche by box

  1. Among all boxes need find biggest box and move it to the vehicle.
  2. Among left boxes needs find biggest box and move it to the vehicle.
  3. Repeat step 1-2, until we have a boxes or have a space at the vehicle

k nearest neighbors

With this algorithm maybe build a suggestion system.
Go deepere, Netflix suggestion system rely on this algorithm.

  1. When user signin, user must rate genres of films and serials which he is liked. After user make it, we convert it to digit information.
  2. After Pythagoras find user with similar preferences
  3. Suggest to user which alredy saw it's neighbors sorting by it's interests.

SHA

SHA is acronim for Security Hash Algorithm. This is secure algorithm. We need it to protect our passwords and other sensetive data
This algorithm accept is input string value, at the output we have hash of given string: god -> 2aec4f....

This algorithm have a only one work direction. You not reverse hash to the string.
Also this algorithm local-insestive. For example if we have two string:dog, dot.
Hash of the both will be different.

Blum Filter's

This filters uses when we need to increase a speed of some operations.
For example we need to check that site is not valid. Problem included that we have a huge table with all sites. And search will be take critical time.
Blum Filters allow us make some guess - site is valid and site is invalid.
Filter is not ideal, by this way we have false positive positives. That makes that not valid site marked as valid. False negatives is excluded.

OCR

OCR as acronim for Optical Character Recognition - algorithm uses at Google Translate for translate immedeatly from the paper. First of all we must study our algorithm about aplhabet. After it, we may compare etalon images with outlines on paper

Discussion (0)

Forem Open with the Forem app