数据结构和算法的集合

项目基地知识图谱硬禾学堂评测工具百科 AI助手发布项目登录/注册

>

>

>

数据结构和算法的集合

收藏

分享

脑图

数据结构和算法的集合

来自GitHub上的Algorithms

Data Structures

Avl Tree (recursive)

Avl Tree (recursive, mildly optimized)

Red Black Tree (recursive)

Binary Search Tree

Dynamic array (integer only, fast)

Dynamic array (generic)

Fenwick Tree (range query, point updates)

Fenwick Tree (range update, point query)

Hashtable (double hashing)

Hashtable (linear probing)

Hashtable (quadratic probing)

Hashtable (separate chaining)

Min Binary Heap

Min Indexed Binary Heap (sorted key-value pairs, similar to hash-table)

Min Indexed D-Heap (sorted key-value pairs, similar to hash-table)

Quad Tree [WIP]

Queue (integer only, fixed size, fast)

Segment tree (pointer implementation)

Segment tree (array based, compact)

Segment tree (pointer implementation)

Skip List [UNTESTED]

Stack (integer only, fixed size, fast)

Stack (linked list, generic)

Suffix Array (O(n²logn) construction)

Suffix Array (O(nlog²(n)) construction)

Suffix Array (O(nlog(n)) construction)

Dynamic Programming

Coin change problem - O(nW)

Edit distance - O(nm)

Knapsack 0/1 - O(nW)

Knapsack unbounded (0/∞) - O(nW)

Maximum contiguous subarray - O(n)

Longest Common Subsequence (LCS) - O(nm)

Longest Increasing Subsequence (LIS) - O(n2)

Longest Palindrome Subsequence (LPS) - O(n2)

Traveling Salesman Problem (dynamic programming, iterative) - O(n22n)

Traveling Salesman Problem (dynamic programming, recursive) - O(n22n)

Minimum Weight Perfect Matching (iterative, complete graph) - O(n22n)

Geometry

Angle between 2D vectors - O(1)

Angle between 3D vectors - O(1)

Circle-circle intersection point(s) - O(1)

Circle-line intersection point(s) - O(1)

Circle-line segment intersection point(s) - O(1)

Circle-point tangent line(s) - O(1)

Closest pair of points (line sweeping algorithm) - O(nlog(n))

Collinear points test (are three 2D points on the same line) - O(1)

Convex hull (Graham Scan algorithm) - O(nlog(n))

Convex hull (Monotone chain algorithm) - O(nlog(n))

Convex polygon area - O(n)

Convex polygon cut - O(n)

Convex polygon contains points - O(log(n))

Coplanar points test (are four 3D points on the same plane) - O(1)

Line class (handy infinite line class) - O(1)

Line-circle intersection point(s) - O(1)

Line segment-circle intersection point(s) - O(1)

Line segment to general form (ax + by = c) - O(1)

Line segment-line segment intersection - O(1)

Longitude-Latitude geographic distance - O(1)

Point is inside triangle check - O(1)

Point rotation about point - O(1)

Triangle area algorithms - O(1)

[UNTESTED] Circle-circle intersection area - O(1)

[UNTESTED] Circular segment area - O(1)

Graph theory

Tree algorithms

Rooting an undirected tree - O(V+E)

Identifying isomorphic trees - O(?)

Tree center(s) - O(V+E)

Tree diameter - O(V+E)

Lowest Common Ancestor (LCA, Euler tour) - O(1)

Network flow

Bipartite graph verification (adjacency list) - O(V+E)

Max flow & Min cut (Ford-Fulkerson with DFS, adjacency list) - O(fE)

Max flow & Min cut (Ford-Fulkerson with DFS, adjacency matrix) - O(fV2)

Max flow & Min cut (Edmonds-Karp, adjacency list) - O(VE2)

Max flow & Min cut (Capacity scaling, adjacency list) - O(E2log2(U))

Max flow & Min cut (Dinic's, adjacency list) - O(EV2) or O(E√V) for bipartite graphs

Maximum Cardinality Bipartite Matching (augmenting path algorithm, adjacency list) - O(VE)

Min Cost Max Flow (Bellman-Ford, adjacency list) - O(E2V2)

Min Cost Max Flow (Johnson's algorithm, adjacency list) - O(E2Vlog(V))

Other graph theory

Articulation points/cut vertices (adjacency list) - O(V+E)

Bellman-Ford (edge list, negative cycles, fast & optimized) - O(VE)

Bellman-Ford (adjacency list, negative cycles) - O(VE)

Bellman-Ford (adjacency matrix, negative cycles) - O(V3)

Breadth first search (adjacency list) - O(V+E)

Breadth first search (adjacency list, fast queue) - O(V+E)

Bridges/cut edges (adjacency list) - O(V+E)

Find connected components (adjacency list, union find) - O(Elog(E))

Find connected components (adjacency list, DFS) - O(V+E)

Depth first search (adjacency list, iterative) - O(V+E)

Depth first search (adjacency list, iterative, fast stack) - O(V+E)

Depth first search (adjacency list, recursive) - O(V+E)

Dijkstra's shortest path (adjacency list, lazy implementation) - O(Elog(V))

Dijkstra's shortest path (adjacency list, eager implementation + D-ary heap) - O(ElogE/V(V))

Eulerian Path (directed edges) - O(E+V)

Floyd Warshall algorithm (adjacency matrix, negative cycle check) - O(V3)

Graph diameter (adjacency list) - O(VE)

Kahn's algorithm (edge list)[UNTESTED] - O(E+V)

Kruskal's min spanning tree algorithm (edge list, union find) - O(Elog(E))

Kruskal's min spanning tree algorithm (edge list, union find, lazy sorting) - O(Elog(E))

Prim's min spanning tree algorithm (lazy version, adjacency list) - O(Elog(E))

Prim's min spanning tree algorithm (lazy version, adjacency matrix) - O(V2)

Prim's min spanning tree algorithm (eager version, adjacency list) - O(Elog(V))

Steiner tree (minimum spanning tree generalization) - O(V3 + V2 * 2T + V * 3T)

Tarjan's strongly connected components algorithm (adjacency list) - O(V+E)

Tarjan's strongly connected components algorithm (adjacency matrix) - O(V2)

Topological sort (acyclic graph, adjacency list) - O(V+E)

Topological sort (acyclic graph, adjacency matrix) - O(V2)

Traveling Salesman Problem (brute force) - O(n!)

Traveling Salesman Problem (dynamic programming, iterative) - O(n22n)

Traveling Salesman Problem (dynamic programming, recursive) - O(n22n)

Linear algebra

Freivald's algorithm (matrix multiplication verification) - O(kn2)

Gaussian elimination (solve system of linear equations) - O(cr2)

Gaussian elimination (modular version, prime finite field) - O(cr2)

Linear recurrence solver (finds nth term in a recurrence relation) - O(m3log(n))

Matrix determinant (Laplace/cofactor expansion) - O((n+2)!)

Matrix inverse - O(n3)

Matrix multiplication - O(n3)

Matrix power - O(n3log(p))

Square matrix rotation - O(n2)

Mathematics

[UNTESTED] Chinese remainder theorem

Prime number sieve (sieve of Eratosthenes) - O(nlog(log(n)))

Prime number sieve (sieve of Eratosthenes, compressed) - O(nlog(log(n)))

Totient function (phi function, relatively prime number count) - O(n1/4)

Totient function using sieve (phi function, relatively prime number count) - O(nlog(log(n)))

Extended euclidean algorithm - ~O(log(a + b))

Greatest Common Divisor (GCD) - ~O(log(a + b))

Fast Fourier transform (quick polynomial multiplication) - O(nlog(n))

Fast Fourier transform (quick polynomial multiplication, complex numbers) - O(nlog(n))

Primality check - O(√n)

Primality check (Rabin-Miller) - O(k)

Least Common Multiple (LCM) - ~O(log(a + b))

Modular inverse - ~O(log(a + b))

Prime factorization (pollard rho) - O(n1/4)

Relatively prime check (coprimality check) - ~O(log(a + b))

Other

Bit manipulations - O(1)

List permutations - O(n!)

Power set (set of all subsets) - O(2n)

Set combinations - O(n choose r)

Set combinations with repetition - O((n+r-1) choose r)

Sliding Window Minimum/Maximum - O(1)

Square Root Decomposition - O(1) point updates, O(√n) range queries

Unique set combinations - O(n choose r)

Search algorithms

Binary search (real numbers) - O(log(n))

Interpolation search (discrete discrete) - O(n) or O(log(log(n))) with uniform input

Ternary search (real numbers) - O(log(n))

Ternary search (discrete numbers) - O(log(n))

Sorting algorithms

Bubble sort - O(n2)

Bucket sort - Θ(n + k)

Counting sort - O(n + k)

Heapsort - O(nlog(n))

Insertion sort - O(n2)

Mergesort - O(nlog(n))

Quicksort (in-place, Hoare partitioning) - Θ(nlog(n))

Selection sort - O(n2)

String algorithms

Booth's algorithm (finds lexicographically smallest string rotation) - O(n)

Knuth-Morris-Pratt algorithm (finds pattern matches in text) - O(n+m)

Longest Common Prefix (LCP) array - O(nlog(n)) bounded by SA construction, otherwise O(n)

Longest Common Substring (LCS) - O(nlog(n)) bounded by SA construction, otherwise O(n)

Longest Repeated Substring (LRS) - O(nlog(n))

Manacher's algorithm (finds all palindromes in text) - O(n)

Rabin-Karp algorithm (finds pattern match positions in text) - O(n+m)

Boyer-Moore (finds pattern match positions in text)[UNTESTED] - O(n+m)

Substring verification with suffix array - O(nlog(n)) SA construction and O(mlog(n)) per query

评论

0 / 100

查看更多

张小宸

2020-03-26

776

硬禾服务号

关注最新动态

0512-67862536

info@eetree.cn

江苏省苏州市苏州工业园区新平街388号腾飞创新园A2幢815室

苏州硬禾信息科技有限公司

友情链接

STEP小脚丫纳芯微电子

Copyright © 2023 苏州硬禾信息科技有限公司 All Rights Reserved 苏ICP备19040198号