algorithms

List of algorithms:

Searching:

Binary search, Lower Bound, Upper Bound

Binary search is an algorithm for finding an object by a given attribute in a set of objects ordered by the same attribute.

Lower bound - returns a position to the first element in the array which is less than value.

Upper bound - returns a position to the first element in the array which is greater than value.

Algorithmic complexity - O(log n), where n is the number of elements in the array.

K-th ordinal statistics

The algorithm finds the K-th largest number in the array, i.e. the K-th ordinal statistic. Algorithmic complexity - O(n), where n is the number of elements in the array.

Sorting:

Insertion sort

Algorithmic complexity - O(n^2), where n is the number of elements in the array.

Merge sort

Algorithmic complexity - O(n log n), where n is the number of elements in the array.

Radix sort (LSD)

Algorithmic complexity - O(n), where n is the number of elements in the array.

Combinatorics:

Permutation

Algorithmic complexity - O(n!), where n is the number of elements in the array.

Subset generation

Algorithmic complexity - O(2^n), where n is the number of elements in the array.

String:

Prefix function

The prefix function of a string is an array of the lengths of the largest self (not equal to the entire substring) prefix of the substring, which is also the suffix of that substring. Algorithmic complexity - O(n), where n is the number of symbols in the string.

Z function

The Z function of a string is an array of length n, the i-th element of which equals the greatest number of characters, starting from position i, that coincide with the first characters of the string. Algorithmic complexity - O(n), where n is the number of symbols in the string.

KMP

The Knuth-Morris-Pratt algorithm (KMP-algorithm) is an efficient algorithm that searches for a substring in a string. Algorithmic complexity - O(m + n), where n is the number of symbols in the text and m is the number symbols in the pattern.

Searching for the minimum period of a string

Algorithmic complexity - O(n), where n is the number of symbols in the text.

String compression

The algorithm finds the shortest “compressed” representation, i.e. such a string t of the shortest length that the original string can be represented as a concatenation of one or more copies of t. Algorithmic complexity - O(n), where n is the number of symbols in the text.

Levenshtein distance

Levenshtein distance (editing distance, editing distance) is a metric that measures modulo the difference between two character sequences. It is defined as the minimum number of one-character operations (namely insert, delete, replace) required to transform one character sequence into another. In general, the operations used in this conversion can be assigned different prices Algorithmic complexity - O(n * m), where n and m are the numbers of symbols in each text.

Search distinct substrings

Algorithm for finding all the different substring of a given string Algorithmic complexity - O(n^2), where n is the number of symbols in the text.

Search longest common substring

An algorithm to find the largest common substring of two strings that has the maximum length. Algorithmic complexity - O(log min(n, m) * max(n, m)), where n and m are the numbers of symbols in each text.

Suffix array

Suffix array - lexicographically sorted array of all string suffixes. Algorithmic complexity - O(n * log n), where n is the number of symbols in the text.

LCP

Algorithm for finding the largest common prefix of two substrings. Algorithmic complexity of construction - O(n), where n is the number of symbols in the string. Algorithmic complexity per query - O(log(n)), where n is the number of symbols in the string.

Aho Corasick

Algorithm of substring search, implements the search for a set of substring from the dictionary in the given string. Algorithmic complexity of construction - O(m), where m is the number of symbols in dictionary. Algorithmic complexity per query - O(n), where n is the number of symbols in the text.

Sheduling:

Johnson’s Algorithm For Scheduling

There are n parts and two machines. Each part must first be machined on the first machine, then on the second one. The i-th part is machined on the first machine in a_i time, and on the second machine in b_i time. Each machine can handle only one part at any given time. You need to create an order of feeding parts to the machines, so that the total machining time of all parts would be minimal. Result is a (order_jobs, total time). Algorithmic complexity - O(n log n), where n is the number of elements in the array.

Data Structures:

disjoint-set-union

This data structure provides the following possibilities. Initially there are several elements, each in a separate (own) set. Two sets can be combined in a single operation, and it is also possible to query which set the given element is currently in. Algorithmic complexity - O(1).

Bloom filter

A Bloom filter is a probabilistic data structure that allows you to check whether an element belongs to a set. It is possible to get a false positive (the element is not in the set, but the data structure says it is), but not a false negative. The Bloom filter can use any amount of memory pre-defined by the user, and the larger it is, the less likely it is to be triggered falsely. The operation of adding new elements to the set is supported, but not deleting existing ones

Segment Tree

A segment tree is a data structure that allows you to find the sum, maximum or minimum on a segment and change individual elements over O(log n). Building a tree over O(n)

Sparse Table

Sparse Table is a data structure that allows you to respond to queries to find a function value on an immutable array on a segment and takes O(1) time and O(n log n) memory, where n is the size of the array. The construction time is also O(n log n)

Sqrt decomposition

Sqrt decomposition is a method, or data structure, that allows you to perform some typical operations (summing up the elements of a subarray, finding the minimum/maximum, etc.). Here is an implementation of finding the sum on a subsection. Algorithmic complexity of construction - O(n), where n is the number of elements in the array. Algorithmic complexity per query - O(sqrt(n)), where n is the number of elements in the array.

Trie

A prefix tree (trie) is a data structure that allows you to store an associative array whose keys are strings. It is a root tree, each edge of which is marked with some character. Algorithmic complexity for all operations(insert, remome, contains) - O(n * log(a)) where n is the length of the string that is queried/deleted/inserted and a is the size of the alphabet, i.e. the number of different characters on the edges of a given prefix tree.

Radix Trie (memory optimization)

Binary Tree

Unbalanced binary search tree. Algorithmic complexity for all operations(insert, remome, get) - O(n) where n is number nodes of tree.

Least common ancestor (LCA)

Algorithmic complexity of construction - O(n). Algorithmic complexity of the query response -O(log n) where n is number nodes of tree.

Graph:

Breadth-first search

Breadth-first search (BFS) is one of the simplest graph traversal algorithms and is the basis for many important graph algorithms. Algorithmic complexity - O(|V| + |E|), where |V| is the number of vertexs in the graph and |E| is the number of edges in the graph.

Depth-first search

Depth-first search (DFS) - one of the methods of graph traversal Algorithmic complexity - O(|V| + |E|), where |V| is the number of vertexs in the graph and |E| is the number of edges in the graph.

Deikstra’s Algorithm

Deikstra’s Algorithm is an algorithm on graphs. It finds shortest paths from one of the vertices of a graph to all other vertices. The algorithm works only for graphs without edges of negative weight. Algorithmic complexity - O(|E| log |V|), where |V| is the number of vertexs in the graph and |E| is the number of edges in the graph.

Сonnected components

Search for connectivity components. The algorithm works with an undirected graph. The algorithm divides the vertices of the graph into several groups, so that within one group one can reach from one vertex to any other, but between different groups there is no path. Algorithmic complexity - O(|V| + |E|), where |V| is the number of vertexs in the graph and |E| is the number of edges in the graph.

Strongly connected components

A strong connectivity component is a subset of vertices (maximal inclusion) such that any two vertices of this subset are reachable from each other. The graph is oriented. Algorithmic complexity - O(|V| + |E|), where |V| is the number of vertexs in the graph and |E| is the number of edges in the graph.

Topological sort

The problem of topological sorting of a graph is as follows: specify such a linear order on its vertices that any edge leads from a vertex with a smaller number to a vertex with a larger number. Obviously, if the graph has cycles, there is no such order. Algorithmic complexity - O(|V| + |E|), where |V| is the number of vertexs in the graph and |E| is the number of edges in the graph.

Checking the graph for cycle

Algorithmic complexity - O(|V| + |E|), where |V| is the number of vertexs in the graph and |E| is the number of edges in the graph.

Kruskal’s algorithm

Kruskal’s algorithm is an efficient algorithm for constructing the minimum spanning tree of a weighted connected undirected graph Algorithmic complexity - O(|E| * log(|E|)), where |E| is the number of edges in the graph.

Bellman-Ford algorithm

The Bellman-Ford algorithm is an algorithm for finding the shortest path in a weighted graph. Unlike Dijkstra’s algorithm, Bellman-Ford’s algorithm allows edges with negative weight, but negative weight loops are still forbidden. Algorithmic complexity - O(|E| * |V|), where |E| is the number of edges in the graph and |V| is the number of vertexs in the graph.

Floid algorithm

This algorithm for finding shortest paths in a weighted graph with positive or negative weights of edges (but no negative cycles). Algorithmic complexity - O(|V|^3), where |V| is the number of vertexs in the graph.

Find subtree sizes

The algorithm finds the size of each subtree. Algorithmic complexity - O(|E|), where |E| is the number of edges in the graph.

Find depth vertices

The algorithm finds the size of each subtree. Algorithmic complexity - O(|E|), where |E| is the number of edges in the graph.

Find bridges

Finding bridges in an undirected graph. Algorithmic complexity - O(|E| + |V|), where |E| is the number of edges in the graph and |V| is the number of vertexs in the graph.

Compression:

Huffman’s algorithm

Huffman’s algorithm is an algorithm for optimal prefix encoding of an alphabet. It is used in many data compression programs, e.g. PKZIP 2, LZH, etc. Algorithmic complexity - O(n log n), where n is the number of elements in the array.

Dynamic programming:

Finding the longest increasing subsequence

Algorithmic complexity - O(log(n) * n), where n is the number of elements in the array.

Longest common subsequence, LCS

The problem of finding the largest common subsequence is the problem of finding a sequence that is a subsequence of two sequences. Algorithmic complexity - O(n * m), where n and m are the numbers of values in each subsequence.

Knapsack problem

From a given set of items with the properties “cost” and “weight”, select the subset with the maximum total cost, while respecting the restriction on total weight. Algorithmic complexity - O(n * m), where n is number things and m is capacity snapsack.

Longest subsequence palindrome

The problem of finding the largest subsequence that can be obtained by crossing out some letters from the given sequence such that the remaining subsequence is a palindrome. Algorithmic complexity - O(n^2), where n is length of string.

Math:

GCD

Algorithm for finding the greatest common divisor. Algorithmic complexity - O(log n), where n is bigest the number from two.

Pow and Pow by mod

Algorithmic complexity - O(log n), where n is pow.

Checking a Number for Simplicity (Fermat’s test)

Algorithmic complexity - O(100 * log n), where n is number.

Find Number Fibonacci

Algorithmic complexity - O(log n), where n is number.

Greedy Algorithms:

Find longest set non intersection segments (with positive coordinates) on line

Algorithmic complexity - O(n * log n + m), where n is number segments and m is the maximum value of the right boundary of the segments