Binary Search
BinarySearch(v, a, lo, hi) input value v array a[lo...hi] of values output true if v in a[lo...hi] false otherwise mid = (lo + hi)/2 if lo > hi return false if a[mid] = v return true else if a[mid] < v return BinarySearch(v, a, mid + 1, hi) else return BinarySearch(v, a, lo, mid - 1)
讯享网
Computing ploynomial
The ploynomial can be recursively computed as
p 0 = a n p_{0} = a_{n} p0=an
p i + 1 = p i x + a i p_{i+1} = p_{i}x+a_{i} pi+1=pix+ai
讯享网Algorithm computingPloynomial(x, n , A[]) p = A[n] for(i = 1; i < n+1; i++){ p = p*x + A[n -1] } return p;
Tree
Computing Depths
O(n)
Algorithm computingDepths(v, d) { v.depth = d; if v has no child return; else for each child v' of v do computingDepths(v', d+1); return; }
Preorder Traversal
讯享网Algorithm preOrder(v){ visit(v); for each child w of v preorder(w); }
Algorithm preOrder(v) if v = null; return; Create an empty stack S; S.push(v); while S is not empty v = S.pop() visit(v) if hsaRight(v) S.push(right(v)) if hasLeft(v) S.push(left(v));
Postordert Traversal
讯享网Algorithm postOrder(v): { for each child w of v postOrder(w); visit(v); }
Algorithm postOrd3erTraversal(v) Create an empty stack S; lastNodeVisited = null; while S is not empty or v != null if v != null //push v and each left descendant onto the stack s.push(v) v = left(v) else topNode = S.top(); //if topNode has a right child not visited before then move to the right child of topNode if topNode.right != null and lastNodeVisited != topNode.right v = topNode.right else //both left and right subtree of topNode has been traversed visit(topNode); lastNodeVisited = S.pop();
Inordert Traversal
only for Binary tree
讯享网Algorithm inOrder(v) { if v has a left child inOrder(v.left) visit(v) if v has a right child inOrder(v.right) }
An inorder traversal of a binary search trees visits the keys in non-decreasing order
Algorithm inOrderTraversal(v) Create an empty stack S; while S is not empty or v != null if v != NULL //keep going left until v = null S.push(v); v = left(v); else v = S.pop() //v has no left child, so visit it visit(v); v = right(v) //go to the tight child
Inorder predecessor(v)
讯享网Algorithm inOrderPredecessor(v) if v= null return null if left(v) != null //V has a left child v = left(v) while right(v) != null v = right(v); return v; else if v is root return null; while parent(v) != null if right(parent(v)) = v //v is the right child of its parent return parent(v); else v = parent(v) return null; //no inorder predecessor
Evaluate Arithmetic Expressions

讯享网
Specialization of a postororder traversal
Algorithm evalExpr(v) { if v is a left node return v.element else x = evalExpr(v.left); y = evalExpr(v.right); operator = operator stored at v, return x <operator> y; }
BST
Search
Time complexity O(n) , 最坏情况:链表(极度不平衡)
讯享网TreeSearch(v, k) Input v(node), k(key) output the node if v is null or v.key = k return v; if k<v.key return TreeSeach(v.left, k); else return TreeSearch(v.right, k);
Insert
be careful: insert equal keys in the left subtree
Time complexity: O(n), 最坏情况:链表(极度不平衡)
TreeInsert(v, k) input v(node), k(key) output none if root = null //empty tree root = CreateNode(k) //create a root to store k else if k < v.key //insert the duplicate keys in the left subtree if v.left = null v.left = CreateNode(k); //insert a new node as left child of v else TreeInsert(v.left, k); else if k > v.key if k > v.key if v.right = null v.left = CreateNode(k); else TreeInsert(v..right, k);
Deletion
Find all entries with key k
讯享网Algorithm findAll(k) Input The search key k, the root v of the binary search tree T Output: A list L containing all the entries with the key k while(v != NULL) if v.key = k findAllEntries(v, L) return L;l else if v.key > k v = v.left else v = v.right return L;
Algorithm findAllEntries(v, L) Input: A node v with the key k and a List L Output: All the entries with the key k in the subtree rooted at v //recursive pre-order traversal to find all entries if v.key = k Add v to L; if v.left != NULL FindAllEntries(v.left, L) if v.right != NULL FindAllEntries(v.right, L) return;
Time complexity:
- Finding the first node with the key k takes O(h) time.
- Since at 2s nodes are visited by findAllEntries(), traversing the subtree rooted at the first node takes O(s) times
Total is O(h + s)
AVL TREE
height of an AVL tree storing n keys is O(log(n))
- a single restructure is O(1)
- find is O(log(n))
- Insert is O(log(n))
- delete is O(log(n))
Splay Tree
- is binary tree
- node is splayed after it is accessed
- splay cost O(h)
- O(h) worst-case is still O(n)
(2, 4)Tree
A (2, 4) tree storing n items has height O(log(n))
Overflow and Split
Insert
讯享网Algorithm insert(k, o) search for key k to locate the insertion node vi //lO(og(n)) add the new entry (k, o) at node vi //lO(1) while (overflow(v)){ //lO(og(n)) if (isRoot(v)) create a new empty root above vi v = split(v); }
Deletion
- visit O(log(n)) nodes
- each fusion and transfer takes O(1) time
- handle an underflow with a series of O(log(n))
deleting an item from a (2, 4)tree takes O(log(n)) time
underflow and Fusion
the adjacent sibling of v are 2-nodes
Fusion operation: merge adjacent sibing and move an entry from parent to the merged node
after a fusion, the under flow may propagate to the parent node

underflow and Transfer
an adjacent sibling is a 3-node or a 4-node
Transfer operation
1. move an item from u to v
2. move an item from w to u
after a transfer, no underfolw occurs
Priority Queue Sorting
Algorithm PQ-Sort(S) Input sequence S Output sequence S sorted in non-decreasing order { Create an empty priority queue P while(! IsEmpty(S)){ e = RemoveFirst(S); Insert(P, e); } while (! IsEmpty(P)){ e = RemoveMin(P); InsertLast(S, e); } }
updating the key of an item in a priority queue
Assume the priority queue is based on a min-heap
讯享网Algorithm updateKey(v) Input: a node v containing the item Output: the heap with the key updated //upheap bubbling while(v != NULL && v.key < parent. key) swap the item of v and its parent v = v.parent //dowmheap bubbling while(v != NULL && v.key > min (v.left.key , v.right.key)) let u be the child of v with the smaller key; swap the item of v and u; v = u;
Time complexity analysis:
- each while loop take O(1)
- each loop is no more than h
- h is O(log(n))
total time complexity is O(log(n))
compute all the items in heap with key less or equal to k
Algorithm lessThanOrEqualToKEntries(H, v) input:A heap H and a node v output: A node list L than contains all the entries with keys less than k if v.key <= k L.add((v.key, v.value)); //add the entry v to the list L if v.leftchild != null LessThanOrEqualToKentires(H, v.leftchild); if v.rightchild != null LessThanOrEqualToKEntries(H, v.rightchild)
this algorithm takes O(n) times where n is the number of entries returned.
Flyers upgrade coupon(base on miles accumulated)
讯享网Algorithm TopKFlyers(A) Input: A list A of n flyers Output: An array B of the top log n flyers Construct a heap H storing all the n flyers, where the key of each flyer Pi is 1/mi for(i = 0; i < log n; i++) B[i] = H.removeMin(); return B
Heap merge(Binary trees)
Algorithm treeUnion(T1, T2) Input: Two trees T1 and T2 that satisfy the heap-order property Output: A tree T that is the union of T1 and T2 and also satisfies the heap-order property v = T1.removeMIN(); //O(h1) let v be the root of T; leftchild(v) = the root of T1 rightchild(v) = the root of T2 apply the down heap bulling to the tree T; //O(h2)
The complexity is O(h1 + h2)
String
Brute-Force Pattern Matching
time complexity is O(nm)
讯享网Algorithm BruteForceMatch(T, P) Input text T of size n and pattern P of size m Output starting index of a substring of T equal to P or -1 if no such substring exists for(i = 0; i < n-m+1; i++){ j = 0; while(j<m && T[i+j] = p[j]) j = j+1 if(j = m) return i; //match at i return -1; //no match anywhere }
Boyer-Moore Heuristics
- the largest index i such that P[i] = c or
- -1 if no such index exists
The last-occurence function can be computed in time O(m+s), where m is the size of P and s is the size of alphabeta
//Boyer-Moore Algorithm Algorithm BoyerMooreMatch(T, P, D){ L = lastOccurenceFunction(P, D) //O(m+n) i = m-1; j = m -1 repeat if T[i] = P[i] //run m-1 times in worst case, before character-jump if j = 0 return i; //match at i else i = i - 1; j = j -1; else //character-jump, run 1 times every m times in worst case l = L[T[i]]; i = i + m - min(j, 1 + l); j = m - 1; until i > n - 1 //run n times in worst case return -1 //no match }

Boyer-Moore’s algorithm runs in time O(nm + s)
The worst case

KMP Algorithm
Preprocessing Pattern
KMP failure Function
preprocesses the pattern to find matches of prefixes of the pattern.
The failure function can be represented by an array and can be computed in O(m) time
讯享网Algorithm failure Function(P) F[0] = 0; i = 1; j = 0; while i < m if P[i] = P[j] //matched j + 1 char F[i] = j + 1; i = i + 1; j = j + 1; else if j >0 //use failure function to shift P j = F[j - 1]; else //no match F[i] = 0; i = i + 1;
The KMP algorithm
The KMP’s algorithm runs in optimal time O(m+n)

Algorithm KMPMatch(T, P) F = failureFuncion(P); i = 0; j = 0; while i < n if T[i] = P[j] //char match if j = m - 1 //match return i - j; else i = i + 1; j = j + 1; else //failure to match if j > 0 j = F[j - 1] else i = i + 1 return -1; //no match
Preprocessing Text
If the text is large, immutable and searched for often, proprocessing the text instead of the pattern
Standard Tries
- O(n) space and support searches
- O(dm) insertion
- O(dm) deletion
n is total size of the string in S
m size of the string parameter of the operation
d size of the alphabet
Compressed Tries
Graph
A graph is a pair (V, E) where
- V is a set of nodes, called vertices
- E is a collection of pairs of vertices, called edges
- Vertices and edges are positions and store elements
Edge type:
- Directed edge(ordered pair of vertices)
- Undiected edge(unordered pair of vertices)
Properties
- ∑ v = 2 m \sum\nolimits_{v} = 2m ∑v=2m
- In an undirected graph with no self-loops and no multiple edges m ≤ n ( n − 1 ) / 2 m \leq n(n - 1)/2 m≤n(n−1)/2
Graph Representations
Adjacency matrix
Advantages
- easily implemented as 2-dimensional asrray
- can represent graph, digraphs and weighted graphs
Disadvantages
- if few edges(sparse) => memory-inefficient
Space complexity is O ( n 2 ) O(n^{2}) O(n2)
Graph Initialization
O ( n 2 ) O(n^{2}) O(n2)
讯享网newGraph(n) input number of nodes n Output new empty graph g.nV = n; g.nE =0; allocate memory to g.edges[][] for all i, j = 0 ... n-1 do g.edges[i][j] = 0; return g;
Edge Insertion
O ( 1 ) O(1) O(1)
insertEdge(g, (v, w)) input : graph g, edge(v, w) if (g.edges[v][w] = 0) g.edges[v][w] = 1; g.edges[v][w] = 1; g.nE = g.nE + 1;
Edge Removal
O ( 1 ) O(1) O(1)
讯享网RemoveEdge(g, (v, w)) Input graph g, edge(v, w) if g.edges[v][w] = 0 g.edge[v][w] = 0; g.edge[w][v] = 0; g.nE = g.nE - 1;
Adjacency lists
Advantages
- relatively easy to implement
- memory efficient if E:V relatively small
Disadvantages:
- one graph has many possible representations unless lists are ordered by same criterion.
space complexity is O ( n + m ) O(n + m) O(n+m)
Graph Initialization
O ( n ) O(n) O(n)
newGraph(n) Input number of nodes n Output new empty graph g.nV = n; g.nE = 0; allocate memory for g.edges[] for all i = 0...n-1 do g.edges[i] = NULL return g
Edge Insertion
O ( 1 ) O(1) O(1) if don’t check for duplicates
讯享网insertEdge(g, (v, w)) Input: graph g, edge (v, w) if inLL(g.edges[v], w) insertLL(g.edges[v], w) insertLL(g.edges[w], v) g.nE = g.nE + 1;
Edge Removal
O ( m ) O(m) O(m)
removeEdge(g, (v, w)) Input graph g, edge (v, w) if inLL(g.edges[v], w) delete(g.edges[v], w); delete(g.edges[w], v); g.nE = g.nE - 1;
DSGs and Topogical Ordering
A digraph admits a topological ordering if and only if it is a DAG
讯享网Algorithm TopologicalSort(G) G1 = G.copy() seq_num = n // assume n is the number of vertices while (G1 is not empty) for each vertex v without outgoing edges v.seq = seq_num seq-- removeFrom(G, v)
BFS
vertex
- unexplored verrtex
- visited vertex
edge
- unexplored edge
- discovery edge
- cross edge
Property
- BFS visits all the vertices and edges
- discovery edges labeled form a spanning tree
Algorithm BFS(G) for v in G.vertexes: v.label= UNEXPLORED for e in G.edges e.label = UNEXPLORED for v in G vertexes: if v.label = UNEXPLORED BFS(G, v)
讯享网Algorithm BFS(G, v) Queue Q v.label = VISITED Q.add(v) while(Q is not empty) v = Q.dequeue() for e in incidentEdges(v) if e = UNEXPLORED w = opposite(v, e) if w = UNEXPLORED w.label = VISITED e.label = DISCOVERY Q.enqueue(w) else e.label = CROSS
Shortest path(unweighted graph)
O(m+n)
Algorithm BFS(G, v) Queue Q for i in G.v create an empty list L[i] for i v.label = VISITED Q.enqueue(v) while( Q is not empty) v = Q.dequeue() for e in incidentEdge(v) if e = UNEXPLORED w = opposite(v, e) if w = UNEXPLORED w.label = VISITED e.label = DISCOVERY Q.enqueue(w) L[w] = L[v] + {v, w} else e.label = CROSS
DFS
vertex
- unexplored vertex
- visited vertex
edge - unexplored edge
- discovery edge
- back edge
Property
- DFS visits all the vertices and edges in the connected component of v
- The discoivery edges labeled by DFS(G, v) form a spanning tree of the connected component of v
DFS (recursive version)
O(m+n)
incidentEdges Function is called
讯享网Algorithm DFS(G) for v in G.v v.label = UNEXPLORED for e in G.v e.label = UNEXPLORED for v in G.v if v = UNEXPLORED DFS(G, V)
Algorithm DFS(G, v) v.label = VISITED for e in v.edges if e.label = UNEXPLORED w = opposite(v, e) if w.label = UNEXPLORED w.label = VISITED e.label = DISCOVERY DFS(G, v) else e.label = BACK
Path Finding
讯享网Algorithm pathDFS(G, v, z) Stack S v.label = VISITED if v = z return S.element() for e in incidentEdges(v) if e.label = UNEXPLORED w = opposite(v, e) if w = UNEXPLORED S.push(e) e.label = DISCOVERY pathDFS(G, w, z) S.pop() else e.label = BACK
Cycle Finding
Dijkstra
Dijkstra(G, s) for each v in G if v = s D[v] = 0; else D[v] = inf Create priority queue Q, which cantain all the vertex of G using D labels as key While Q is not empty u = Q.removeMin() for w in AdjacentNodes(u) if D[w] > D[u] + {u, w} //relax D[w] = D[u] + {u, w} w.from = u Q.update(w) return the label D[u]
Bellford
O(mn)
讯享网Algorithm Bellford(G, s) for each vertex v in G if v = s D[v] = 0 else D[v] = inf for (i = 1; i < n - 1; i++) u = G.origin(e) z = G.opposite(u, e) r = D[u] + weight if D[z] > r z.from = u D[z] = r
Kruskal’s
for each vertexs create a cloud of {v} create a priority queue Q and insert all edges using their weight as the key T = empty while Q is not empty e = Q.removeMin() u, v = the endpoint of e if cloud(u) != cloud(v) add e to T merge cloud(u) and cloud(v) return T
Prim
讯享网Algorithm PrimJarnikMST(G) Pick any vertices v of G D[v]= 0 for each u in G.vertices with u != v D[u] = inf Create a priority queue Q with an entry ((u, null), D[u]) D[u] is the k while Q is not empty (u, e) = Q.removeMin(); T.add(e) for v in AdjacentNode(u) D[v] = weight(u, z) update all element (z, (u, z)) Change D[z] return T
LCS
Algorithm LCS(x, y) Array L[x.len + 1][y.len + 1] = {0} for i in range( x.len) for j in range( y.len) if x[i] = y[j] L[i][j] = L[i - 1][j - 1] + 1 else L[i][j] = max(L[i - 1][j], L[i][j - 1]) return L
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/77063.html