2025年9024复习

9024复习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 gt hi return

大家好,我是讯享网,很高兴认识大家。

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​=pi​x+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:

  1. Finding the first node with the key k takes O(h) time.
  2. 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:
  1. Directed edge(ordered pair of vertices)
  2. Undiected edge(unordered pair of vertices)
Properties
  1. ∑ v = 2 m \sum\nolimits_{v} = 2m ∑v​=2m
  2. 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

  1. BFS visits all the vertices and edges
  2. 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

  1. DFS visits all the vertices and edges in the connected component of v
  2. 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 
小讯
上一篇 2025-03-06 11:20
下一篇 2025-01-12 07:14

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/77063.html