MindMap Gallery Introduction to Algorithms
Summary of introductory knowledge on algorithms, which introduces the concept of algorithms, algorithm expressions, algorithm complexity analysis, algorithm design steps, etc. It is the basis for computer algorithm design and analysis and lays the foundation for learners to master various specific algorithms in the future. It is Important content that must be learned in the process of learning algorithms.
Edited at 2024-03-02 22:28:38Avatar 3 centers on the Sully family, showcasing the internal rift caused by the sacrifice of their eldest son, and their alliance with other tribes on Pandora against the external conflict of the Ashbringers, who adhere to the philosophy of fire and are allied with humans. It explores the grand themes of family, faith, and survival.
This article discusses the Easter eggs and homages in Zootopia 2 that you may have discovered. The main content includes: character and archetype Easter eggs, cinematic universe crossover Easter eggs, animal ecology and behavior references, symbol and metaphor Easter eggs, social satire and brand allusions, and emotional storylines and sequel foreshadowing.
[Zootopia Character Relationship Chart] The idealistic rabbit police officer Judy and the cynical fox conman Nick form a charmingly contrasting duo, rising from street hustlers to become Zootopia police officers!
Avatar 3 centers on the Sully family, showcasing the internal rift caused by the sacrifice of their eldest son, and their alliance with other tribes on Pandora against the external conflict of the Ashbringers, who adhere to the philosophy of fire and are allied with humans. It explores the grand themes of family, faith, and survival.
This article discusses the Easter eggs and homages in Zootopia 2 that you may have discovered. The main content includes: character and archetype Easter eggs, cinematic universe crossover Easter eggs, animal ecology and behavior references, symbol and metaphor Easter eggs, social satire and brand allusions, and emotional storylines and sequel foreshadowing.
[Zootopia Character Relationship Chart] The idealistic rabbit police officer Judy and the cynical fox conman Nick form a charmingly contrasting duo, rising from street hustlers to become Zootopia police officers!
Introduction to Algorithms
Algorithm concept
The basic meaning of algorithm
a method of solving a certain problem
Definition of algorithm
informal description
An algorithm is a finite set of well-formed rules. It specifies a series of operations to solve a specific type of problem. It is a method or process for solving a problem. It is a sequence of instructions that satisfy input, output, certainty, and finiteness.
Input: There are zero or more external quantities that serve as input to the algorithm.
Output: The algorithm produces at least one quantity as output.
Deterministic: Each instruction that makes up the algorithm is clear and unambiguous.
Finiteness: Each instruction in the algorithm has a limited number of executions, and the time to execute each instruction is limited.
Algorithms and Programs
A program is the specific implementation of an algorithm in a certain programming language.
The program does not need to satisfy the algorithm's property (4), that is, finiteness, such as an operating system.
Program = programming language algorithm data structure
The scope of algorithm research
Numeral Calculations
Linear nonlinear equations, interpolation, integral differential
non-numerical calculations
Sorting, optimization, coloring, path, traversal, machine learning, data mining
properties of algorithms
correctness
If for any given valid input, the algorithm always gives the correct answer to the problem within a limited time, then the algorithm for solving the problem is said to be correct.
This mainly refers to the mathematical correctness of the algorithm. Because mathematical correctness is the basis for program correctness. When formulating an algorithm, give a mathematical proof of its correctness.
workload
Measured by execution time
Depends on the specific execution machine, not good
Measured by the number of basic operations
Independent of the computer on which it is executed
Space usage
The space required except the storage space for programs and input data
Works in-place: extra space usage is a constant function of input size
simplicity
The algorithm should be intuitive, clear and easy to read. A simple algorithm should be easy to prove its correctness and easy to analyze the workload.
optimality
An abstract mechanism for expressing algorithms
Language level abstraction
high level programming language
1. Close to algorithmic language, easy to learn and master
2. Provide programmers with a structured programming environment and tools. The program has good readability, maintainability and high reliability.
3. Does not rely on machine language, has good program portability and high reusability
4. The compiler handles trivial matters, so the degree of automation is high, the development cycle is short, and the program quality is high.
data level abstraction
abstract data type
An abstract data type is a data model of an algorithm together with a set of operations defined on the model that serve as building blocks of the algorithm.
advantage
(1) The top-level design of the algorithm is separated from the bottom-level implementation;
(2) Algorithm design is separated from data structure design, allowing free choice of data structure;
(3) The data model and the operations on the model are unified in ADT, which facilitates the trade-off between space and time consumption;
(4) Algorithms expressed in abstract data types have good maintainability;
(5) The algorithm is naturally modular;
(6) Provide effective ways and tools for top-down gradual refinement and modularization;
(7) The algorithm has a clear structure and distinct layers, which facilitates the proof of algorithm correctness and complexity analysis.
Describe algorithm
Java
Program structure
type of data
method
abnormal
Java classes
general method
garbage collection
recursion
Steps of Algorithm Design
Basic steps of algorithm design
1. problem statement
2. Modeling
3. algorithm design
4. Algorithm correctness proof
5. Algorithm implementation
6. Algorithm complexity analysis
7. Experimental test
8. Documentation
Algorithm complexity analysis
Analysis reason
For an algorithm to successfully process a specific input, the memory space and running time required by the algorithm need to be estimated or bounded
Can quantitatively compare the efficiency of different algorithms for the same problem
Complexity Classification
Polynomial time complexity algorithm
Exponential time complexity algorithm
Experimental testing and analysis
reason
Experiment to verify the correctness of the algorithm
Determining the Experimental Quality of Algorithms
Determine the computational limits of an algorithm
method
Choice question: What to test, purpose of testing
Estimate the average asymptotic running time of an algorithm
Compare the performance of similar algorithms for a given input
Experiment to determine parameters in the algorithm
For approximation algorithms, how close the test results are to the optimal value
Determine metrics
Actual running time
interference factors
Other programs running on your computer
cache impact
memory utilization
Generate test data
sufficient quantity
different scales
different distribution
Program and run
programming
Ensure programming level consistency
run
Ensure a clean computing environment and reduce data noise
data analysis
ratio test
Power test
Documentation
Problem description and analysis
Modeling and Solving
Algorithm design and correctness proof process
Algorithm complexity analysis
Test result recording and analysis report
Input/output requirements and format description
Algorithm complexity analysis
Use T(N,I) to represent the time complexity of algorithm A on an abstract computer.
N: the size of the problem to be solved
DN: the set of all possible inputs of size N
P(DN): Probability distribution of DN
I: input to the algorithm, I∈DN
time complexity measure
Symbol Description
O
definition
mathematical formal definition
O(g(n)) are all functions with g(n) as the upper bound
symbolic understanding
Arithmetic rules
Proof for (1)
Ω
definition
mathematical formal definition
θ
definition
mathematical formal definition
o
definition