Wondershare EdrawMind
マインドマップギャラリー Algorithm Analysis and Design
- 169
- 1
Algorithm Analysis and Design
A mind map about algorithm analysis and design. An algorithm is a calculation that satisfies the conditions of termination, certainty, feasibility, input and output. No matter which algorithm is used to find the optimal solution, it must be clear what the optimal solution is.
2023-10-28 17:00:08 に編集されました
- おすすめ
- アウトライン
Algorithm Analysis and Design
chapter1Introduction
An algorithm is a calculation that satisfies the following conditions
Purpose: solve problems
Terminability
certainty
feasibility
enter
output
calculate
给定计算模型机械的执行的规则或计算步骤序列被称为计算
一个计算机程序是一个计算
Calculation is not an algorithm
question
Defines the relationship between input and output
Algorithm Autumn Festival is a complete problem, not a simple problem instance
Analysis algorithm
Algorithm correctness: terminates for all inputs and produces correct outputs
Incorrect algorithm: does not terminate or produces incorrect output for an input
Correctness of approximate/stochastic algorithms: terminates for all inputs, produces approximately correct solutions or a small number of incorrect solutions
Reasons for correctness proof
Debugging programs cannot prove that there are no errors
method
Terminate on all input
Every input has the correct output
algorithm complexity
Purpose: Analyze the amount of resources required by the algorithm for different inputs
Time complexity, space complexity, number of inputs and outputs, etc.
input size function
Input size: size(α)
Instance time complexity: the number of operations that are most needed to produce a result for a specific input
Time complexity of a specific input
Instance space complexity
specific input
空间复杂性，对输入产生结果所需要的存储空间大小
是输入大小的函数S(n)
Worst time complexity
algorithm minimum complexity
average algorithm complexity
Probability of occurrence multiplied by the sum of all possibilities of complexity
Algorithmic Analysis Model
random access model
Parallel multiprocessor model
Time complexity analysis
It’s not that a program takes much time to solve a problem, but that the time length increases very quickly when the scale of the problem expands.
Constant level time complexity
Time complexity analysis of direct insertion algorithm
When reading the kth number, compare it positively with the previous number,
Algorithm correctness analysis
loop invariant method
Loop invariant P: the data and data structures operated on have key properties
For example, in a sorting algorithm, the property that the order of numbers does not change can be used as a loop invariant.
loop initialization
Cycle steps
loop terminated
design algorithm
divide and conquer
dynamic programming
greedy algorithm
tree search algorithm
Problem division
Turing machine
P of the problem solved by a deterministic Turing machine in polynomial time
Problems NP solvable by an uncertain Turing machine in polynomial time
Uncertain Turing machines can no longer be Non-NP
subtopic
Chapter 2 Math Basics
2.1 Computing the order of the complexity function
The set of functions of the same order f(x)=θ(g(x)) where the set of functions is: θ(g(x)) tight bound
The upper bound of the low-order function f(n)=0(g(n)) may be a lower-order upper bound than it
Higher-order function f(n)=Ω(g(n)) lower bound best case
It cannot explain the size relationship, it can only explain the class relationship; a higher-order function is not necessarily greater than its lower bound; especially a higher-order function [not a strictly higher-order function]
θ(g(n))⊆0(g(n)) f(n)=O(n^k ) Polynomial bound
Strictly low-order function upper bound but not tight bound f(n)=o(g(n))
f(n)=o(g(n))⇒(lim)┬(n→∞) f(n)/g(n) =0
Strictly higher-order function lower bound but not tight bound f(n)=ω(g(n))
f(n)=ω(g(n)) if and only if g(n)=o(f(n))
f(n)=ω(g(n))⇒(lim)┬(n→∞) f(n)/g(n) =∞
properties of the order of a function
Transitivity includes the above five
Reflexivity includes the first three
Symmetry tight bound
antisymmetry
f(n)=0(g(n)) if and only if g(n)=Ω(f(n))
f(n)=o(g(n)) if and only if g(n)=ω(f(n))
The meaning of function order in mathematical formulas
2.2 Estimation and bounds of sum
linear sum
series
Bounds for direct summation
subtopic
subtopic
2.3 Recursive equations use themselves to define themselves
Three Main Methods for Solving Recursive Equations
Substitution Guess Mathematical Induction
Iterate and convert into a sum, estimate the sum
Master theorem
subtopic
Chapter3 Sorting and Divide and Conquer Algorithms
3.1 Principle of divide and conquer
design phase
Points: sub-problems may not be the same. Divide time D(n)
Governance: Solve each sub-problem aT(n)
Sum: combine solutions to subproblems C(n)
Total time complexity: T(n) = a(T(n/b)) D(n) C(n)
analysis stage
Build recursive equations
Solve
3.2 Sorting algorithm based on divide and conquer
The main job of quick sort is to perform the partitioning algorithm and need to know the boundary conditions
Lower bound for the sorting problem
3.3 Median and order statistics
principle of reduction
For example, search by half
Select question
3.4 Find the closest point pair
Methods of dividing and merging to reduce f(n)
One-dimensional space algorithm
Sort first
divide and conquer algorithm
point
rule
and
Two-dimensional space algorithm
3.5 Sorting in linear time
Counting
Use three arrays A, B, and C
The overall idea: input array-A, output array: B, counting array: C [array base is the value range of A [0-k [maximum value in A]]] (requirement: A needs to be an integer array)
[Note] Use the bucket structure when space consumption is large.
Problems
A[i] is an integer
And the value range of the input array 0-k needs to be smaller, otherwise the efficiency will be greatly reduced.
During the sorting process, a counting space of max length and an auxiliary output space of length len are required. This space is relatively large, and the space complexity is O(len max).
Time complexity: O(n k)
Radix
Features
stable
Sort from lowest to highest
algorithm
Input requirements: Array integers with the same number of digits d
Time complexity: O(d(n k[input value range, the impact is relatively small and can be ignored]))
Problem: d is too large
Extended using a divide-and-conquer algorithm
Divide the array with b digits into b/r and take the entire data with r digits upward. The value range of each data is 0-2^r-1
Sort using count
The optimal value of r: lgn rounded down
Note: It can be used when r is not large.
Bucket sorting
An assumption of bucket sorting: the input is independently and uniformly distributed between 0-1 [conditions expected to achieve linearity]
Bucket sorting idea
Divide 0-1 into evenly sized buckets
Input is sorted into buckets
Sorting data in buckets
List all sorted data in each bucket
Time complexity: tight bound n
Some criteria for judging algorithms
stable：按照输入顺序合理的排序输出
in-place：没有另外开辟空间
3.6 Find the convex hull
problem definition
Input: a collection of points on the plane, output convex hull
nature
For a convex polygon P, the sides connecting any two points in P are all within P.
Graham-Scan algorithm
Counterclockwise, sorted by polar angle size
Rotate to the left
Notice
The maximum and minimum values of xy are all on the convex hull. First, determine one of the points as the starting point, draw a horizontal line, and traverse the above points starting from this horizontal line [the smallest point is selected]
pseudocode
Find the point in Q with the smallest y-coordinate value
Sort the remaining points in Q counterclockwise
Push into stack S
If the composition fee moves to the left, pop the top element of the stack out
Time complexity: f(n)=0(n logn)
Correctness analysis: Loop invariant [Before processing a certain node, stack S stores CH (Qi-1) from bottom to top]
divide and conquer algorithm
Boundary conditions
point
Divided into Ql, Qr
rule
and
Just run Graham-Scan on the merged sequence
How to merge sequences
3.7 Fast Fourier Transform FFT
3.8 Integer multiplication
Optimize the division stage to reduce a
Problem definition: Input - n-bit binary integers X and Y; output - the product of X and Y
chapter 4 Dynamic programming algorithm
Algorithm summary
There is a feeling of exhaustion
就是罩子问题和服问题之间的关系之后再使用穷举的方法最后选定最小值作为最优解
注意：覆盖所有情况
4.1 Elements of dynamic programming
Reason: If the sub-problems are not independent of each other, the score method will repeatedly calculate the common sub-problems, which is very inefficient.
Purpose: Optimization problem - The optimization problem is to give a cost function, in Search the solution space of the problem for the optimal solution with minimum or maximum cost
Dynamic programming problems are a common approach to solving optimization problems
Definition: The original problem is divided into a series of sub-problems [number of polynomial levels]
Solving subproblems bottom-up
Top-down divide-and-conquer algorithm
Scope of application: a type of problem that can be solved in a similar way, where sub-problems can be reused
Conditions of Use
Optimizing substructure: When the optimal solution of a problem contains the optimal solution of a subproblem, we say that this A problem has an optimization substructure.
Overlapping subproblems: During the solution process of the problem, the solutions to many subproblems will be used multiple times.
When there is no overlap, just use divide and conquer, otherwise you will need to create additional storage space.
Algorithm design steps
– Analyze the structure of the optimal solution [which sub-problems are composed of optimal solutions, just go to the boundary conditions] – Recursively define the cost of the optimal solution – Divide subproblems recursively until they are indivisible – Solve each sub-problem bottom-up – Calculate the cost of the optimization solution and save it – Obtain information to construct the optimal solution – Construct an optimal solution based on the information used to construct the optimal solution
4.2 Matrix chain multiplication
Problem definition: input p_i-1*p matrix; output the method to calculate the minimum cost
Matrix multiplication
Satisfy the associative law, different calculation orders will have different costs
Use dynamic programming methods
Have overlapping sub-problems
Recursively define the cost of the optimal solution
subtopic
Extended solution: You can use memorization method, and the score can be turned into dynamic programming.
4.3 Longest common subsequence
problem definition
problem solving
⚫ Structural analysis of optimized solution ⚫ Establish cost recursive equation for optimal solution ⚫ Divide subproblems recursively ⚫ Calculate the cost of the optimized solution from the bottom up and record the construction information of the optimized solution ⚫Construct optimization solution
Optimized substructure analysis
i-th prefix: Xi
Optimize substructure
Convenient to use this method for recursive solution
Three direct proofs
Sub-problem overlap, number of problems that need to be processed (at most mn sub-problems)
It is best to cover all situations
To facilitate the calculation of boundary conditions
If the boundary conditions are inconvenient to calculate, it will take at most O(m) or O(n) time to calculate the boundaries.
Problem division: Use the conditions defined above, that is, the conditions defined previously for recursion
Calculate the optimization solution cost from the bottom up and then solve downward based on the above solution.
Finally, solve from the bottom up and solve according to the symbol of the optimal solution marked by B. The solution obtained is the inversion of the final solution.
Pseudocode: The solution is found by rows, and the arrows are used to search from the bottom up.
Time complexity: O(mn) [number of sub-problems], where the time to construct the optimal solution is O(m n)
Space complexity O(mn)
Space optimization strategy: You can design C into only two rows and m columns or something like that
4.4 0/1 backpack problem
problem definition
Develop a packing strategy that maximizes the value of the items in the bag without being overweight
Preliminary analysis: There are two options for each item, to install or not to install; the calculation cost of the installation and removal plan is n [after calculating the tea cup/value, use constant time to compare to obtain the maximum value]
The total calculation cost is O(n2^n)
np complete problem
problem solving
Structural Analysis of Optimized Solution
Overlap of sub-problems: When the weights of the items are the same and both are 1, there will be a large number of overlapping sub-problems.
Not suitable for divide and conquer algorithm [you can try to use memoization]
problem definition
Establish a recursive equation that optimizes the solution cost
Define the cost matrix m;
m[i,j]
i:起始的、计算子问题优化解的代价的矩阵时间
j:指的是包的容量
Summary of recursive equations
Recursive partitioning subproblem
What you need to know to calculate m[i,j]
Calculate the cost of the optimized solution from the bottom up and record the construction information of the optimized solution
Construct optimization solution
Total cost calculation: pseudopolynomial algorithm
There are four situations in total
4.5 Binary search tree
problem definition
Binary search tree definition
Affects the overall query cost of the search tree: the shape of the tree and the query probability of the node
expected value of tree
Odd-numbered nodes are leaf nodes
Even-numbered nodes are internal nodes
Expected cost value of E(T) tree
The cost value is related to the depth of the tree and the cost increment.
The root node must be an even number
problem solving
Structural Analysis of Optimized Solution
Optimized substructure and proof
The contribution value of the subtree: the subtree’s position is fixed, its probability is fixed, and its contribution difference is the lone star.
Contribution increment: probability * depth difference
Use optimization substructures to construct optimal solutions
sub-problem overlap
Establish a recursive equation that optimizes the solution cost
Establish search cost recursive equation for optimal solution
Boundary conditions and other considerations
all covered
Formula: Probability (cost increment) [left subtree right subtree]
W: Increment; E: Expected cost; P: Probability
Incremental recursive calculation formula
W[i,j] = w(i,j-1) pi pj = w(i,r-1) w(r 1,j) pr
Recursive partitioning subproblem
Calculate the cost of the optimized solution from the bottom up and record the construction information of the optimized solution
Construct optimization solution
4.6 Minimum edit distance
definition
Convert between two strings
It only contains three operations: inserting characters, deleting characters, and replacing characters [each one counts as a basic operation]
Character alignment affects efficiency
Solve
Structural Analysis of Optimized Solution
Properties of minimum edit distance
Non-overlapping: Any character can only perform at most one operation
order independence
symmetry
empty extended string
sub-problem overlap
Establish a recursive equation that optimizes the solution cost
four situations
Boundary conditions
First, you need to consider the boundary conditions as the conditions required for the starting calculation.
Algorithms and Algorithmic Complexity
Time complexity O(mn)
Space complexity: O(mn)
Optimize space structure
Recursive partitioning subproblem
Calculate the cost of the optimized solution from the bottom up and record the construction information of the optimized solution
Construct optimization solution
Minimum edit distance discrimination problem
application
字符串的相似度查询
definition
input Output
analyze
The minimum edit distance is not less than the absolute value of the length of the two
Complexity
Two situations that do not require calculation
The length difference is greater than the input decision threshold
The calculation is required to use the above result value greater than 2
space complexity
O(min{m,n}t): can be optimized
O(t)
time complexity
O(min{m,n}t)
Each row/column can calculate at most 2*t 1
chapter5 greedy algorithm
The difference from the previous two algorithms
子主题
贪心算法：原问题进行选择获取剩余子问题直至子问题为空
delicate
前面两种：原问题划分为子问题，繁重，自底向上
5.1 Basic principles
basic concept
Approximate algorithms, heuristic algorithms
Local optimal solution, the best choice at the moment
example
Exchange coin problem
Regional scheduling problem
use
Solve optimization problems
Basic idea
An algorithm for solving an optimization problem consists of a series of steps, each step having a set of choices to make the best choice at the moment.
Hope to achieve the global optimal solution
Try it step by step, then overload and try other things to find the greedy algorithm
Gradually approach or even finally reach the optimal solution
Example
Conditions for generating optimal solutions
Optimize substructure
Greedy selective
Induction
Summarize the algorithm steps or summarize the problem
Each step is better than other algorithms and produces an optimal solution
The solution for each step included does not necessarily need to be a good solution for the included step
commutative argument
More convenient
Under the premise of unchanged optimality, gradually replace from an optimal solution to finally obtain the solution of the greedy algorithm.
Compare
design steps
design steps
greedy selection algorithm
remaining subproblem
need proof
对于贪心选择来说，所求解的问题具有优化子结构
对于贪心选择算法莱说，具有Greedy选择性
5.2 Activity selection issues
problem definition
problem solving
Designing a Greedy Selection Method
Structural Analysis of Optimized Solution
Greedy selective proof
Lemma 1
Demonstrating Greedy selectivity
[Note] It is necessary to clarify what are the conditions for the optimal solution In this problem, the optimal solution is the most consistent activity Depends on quantity and compatibility characteristics
Lemma 2: Optimize substructure
proof by contradiction
Lemma 3
algorithm design
Algorithm complexity analysis
5.3 Huffman coding
problem definition
binary character encoding
fixed length encoding
variable length encoding
prefix encoding
definition
coding tree
The cost of coding trees: the cost is the expected sum of depth
C: character set
B: sum of costs
F: frequency
Greedy thoughts
Cyclically select the two nodes with the lowest frequency to generate a subtree until a tree is formed
problem solving
Designing a Greedy Selection Method
Method of choosing
The structure of the remaining subproblem
Structural Analysis of Optimized Solution
Lemma 1: Proof of optimized substructure
Lemma 2: The deepest position, the two characters of the minimum appointment letter, the same maximum length
greedy selectivity
Optimize the prefix tree to contain the maximum length of two nodes at the same depth
Greedy selective proof
algorithm design
Algorithm complexity analysis
5.4 Minimum spanning tree
problem definition
Kruskal algorithm
design
Optimize solution structure
remaining subproblem
shrink operation
expansion operation
Optimized substructure proof
Greedy selective
Algorithmic complexity
algorithm correctness
Prim's algorithm
design
Optimize solution structure
Greedy selective
Algorithmic complexity
summary
Generic algorithm
frame
Basic idea
Algorithm Description
greedy selectivity
definition
Cut(S,V-S)
Cross Cut
Comply with the Cut of edge set A
Across the light edge of the Cut
Theorem 1
Kruskal: Find light edges across Cut that follow A [contains a series of connected components] and points not included in A
Prim's algorithm
review
Minimum completion time 5.5 Minimum Mackspan Scheduling
problem definition
approximation algorithm
Performance analysis
chapter6 amortization analysis
Fundamental
Basic idea
Stack operations: ignore data structures and relationships between operations
Amortized analysis method
Purpose: Analyze the upper bound on the cost of n operations on a given data structure
The cost of each operation is analyzed equally through the total cost [upper bound]
What is determined is an upper bound, not a probability
aggregation method
average
accounting methods
Prepayment [associated with the data object, the credit of the data object]
potential energy method
Accumulated potential [associated with the entire data structure, energy]
aggregation method
analyze
分析过程中要精细化，注意每个操作之间的关联
用数据对象上小的操作代价来来预付之后的大的操作代价
Related operations
比如multipop的多次是因为前面多次的push，所以需要push操作为他负责
Principle: Different operations are given the same cost
The sum of all operations, on each element of n
binary counter
A total of lgn bits
accounting methods
principle
Prepayment [associated with the data object, the credit of the data object]
Selection principle: The credit stored in the data structure is non-negative
Example
analyze
分析过程中要精细化，注意每个操作之间的关联
用数据对象上小的操作代价来来预付之后的大的操作代价
Related operations
比如multipop的多次是因为前面多次的push，所以需要push操作为他负责
Stack operations
push, pop, multipop
Each object will be ejected at most once after standing
Proof about upper bound:
binary counter
Set 0 Set 1
Major operation: set to 0
potential energy method
There is also the final proof about the upper bound.
可以使用放缩
实际的代价小于一个值
或者平摊大于
或者都有
principle
example
stack
Potential energy definition
Binary addition
focus
势能定义
It is best to define the total number of objects increased by small operations
比如说是栈：pop，占中总的对象数目
二进制加法：1的个数
使得总势能大于等于0
就是在每一次操作之后势能都是大于0的
大操作小操作
focus
分清楚谁是大操作，谁是小操作
用小的操作代价来来预付之后的大的操作代价
Dynamic table amortization analysis
concept
Operations supported by dynamic tables
Data structure: Use an array to implement a dynamic table
Loading factor: not less than a constant
express
table[T]
num[T]
size[T]
expansion and contraction
Dynamic table expansion
Aggregation analysis
Analysis conditions and fine analysis
accounting methods
Actual insert operation cost
own savings for expansion
Expansion: big operations
Insert: small operations
Give him the corresponding first object without deposit.
Charge for insertion
Potential energy analysis
Shrinking of dynamic tables
The time needed to buffer the table
potential energy method
When the major operation is completed, the potential energy is at least 1
As the primary key for small operations approaches the time point when large operations are required, the potential energy gradually increases.
Draw strength for big operations
When the key point is reached, it will be the potential energy needed for big operations.
relation
之间有一个二倍
1/4的关系
num在大操作之后是size的一半
Big operations are contraction and expansion operations 3
而前面的小操作改变的都是num
势能在小操作的过程中一定是增加的需要注意
The total must increase during the small operation! ! ! ! ! ! ! !
Note: No matter which algorithm is used to find the optimal solution, it must be clear what the optimal solution is.