Algorithm
Introduction to Algorithms
An algorithm is a well-defined, finite sequence of executable steps designed to solve a specific problem. It takes input data, performs a limited number of operations, and produces a definite output. As the core driving force of computer science, algorithms are closely intertwined with data structures—data structures provide the carrier for storing data, while algorithms endow data structures with processing capabilities. From simple numerical calculations to complex artificial intelligence decision-making, algorithms play a pivotal role in all these scenarios.
I. Background and Fundamentals
1. Development Background
The concept of algorithms did not emerge with the invention of computers; its history can be traced back thousands of years:
- Ancient Algorithm Embryos: Around 300 BC, Euclid proposed the Euclidean algorithm (for finding the greatest common divisor of two numbers), one of the earliest classic algorithms. Ancient Chinese methods such as Qin Jiushao algorithm (for polynomial evaluation) and Geng Xiang Jian Sun Shu (for fraction reduction) also belong to the early forms of algorithms.
- Modern Theoretical Foundation: In the early 20th century, mathematician David Hilbert's "Entscheidungsproblem" (decision problem) promoted the development of algorithm theory. In 1936, Alan Turing proposed the Turing machine model, which theoretically defined the essence of algorithms and laid the mathematical foundation for modern algorithms.
- Boom in the Computer Era: With the invention and popularization of computers, algorithms transitioned from theory to practice. A series of classic algorithms such as sorting, searching, and dynamic programming emerged to address practical problems like data processing, resource scheduling, and path planning. In the era of big data and artificial intelligence, machine learning algorithms and deep learning algorithms have become new research and application hotspots.
Today, algorithms have penetrated all walks of life. From daily mobile navigation and e-commerce recommendations to cutting-edge autonomous driving and gene sequencing, all rely on efficient algorithms for support.
2. Core Fundamentals
Five Key Characteristics of Algorithms
- Input: Zero or more inputs that describe the initial state of the problem.
- Output: One or more outputs that represent the solution to the problem (a sequence of steps without output cannot be called an algorithm).
- Finiteness: The algorithm must terminate after a finite number of steps and cannot fall into an infinite loop.
- Definiteness: Each step has a clear and unambiguous meaning, and the same input will always yield the same output.
- Effectiveness: Each step can be implemented through a finite number of basic operations.
Algorithm Performance Evaluation
The core indicators for evaluating the pros and cons of an algorithm are complexity metrics, including time complexity and space complexity. Both are described using Big O notation, reflecting the trend of complexity growth as the data scale $n$ increases.- Time Complexity: The amount of computational work required for the algorithm to execute, focusing on the growth trend of the number of execution steps rather than the actual execution time. Common complexities sorted from lowest to highest are: $O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)$.
- Space Complexity: The amount of storage space required during the algorithm's execution, including input data space, program space, and auxiliary space. In resource-constrained scenarios (e.g., embedded devices), optimizing space complexity is particularly important.
Algorithm Design Principles
A good algorithm should follow four core principles: correctness, readability, efficiency, and robustness.- Correctness: It can correctly solve the problem, process all legal inputs, and produce expected results.
- Readability: The steps of the algorithm are clear and easy to understand, facilitating debugging, maintenance, and reuse.
- Efficiency: Time complexity and space complexity are minimized as much as possible, balancing execution speed and resource usage.
- Robustness: It can handle illegal inputs (e.g., abnormal values, boundary values) without causing program crashes.
II. Various Types of Algorithms
Algorithms are diverse and can be categorized into the following major types based on problem scenarios and core ideas. Each type of algorithm has its typical applications and core characteristics.
1. Sorting Algorithms
Sorting algorithms are used to arrange a set of data in a specified order (ascending or descending). They are one of the most basic and widely used types of algorithms. Based on core strategies, they can be divided into comparison-based sorting and non-comparison-based sorting.
| Algorithm Category | Typical Algorithms | Core Idea | Average Time Complexity | Space Complexity | Stability | Applicable Scenarios |
|---|---|---|---|---|---|---|
| Comparison-based Sorting - Exchange Sort | Bubble Sort | Compare adjacent elements pairwise, swap them if they are in reverse order, and "bubble" the largest/smallest value to the end in each round | $O(n^2)$ | $O(1)$ | Stable | Small-scale data sorting, teaching demonstrations |
| Quick Sort | Select a pivot element, partition the data into two parts ("less than pivot" and "greater than pivot"), and recursively sort the subarrays | $O(n log n)$ | $O(log n)$ (recursion stack) | Unstable | Large-scale data sorting (mainstream in industry) | |
| Comparison-based Sorting - Insertion Sort | Insertion Sort | Insert unsorted elements one by one into the appropriate position in the sorted sequence | $O(n^2)$ | $O(1)$ | Stable | Small-scale data, nearly sorted data |
| Shell Sort | Perform insertion sort on groups divided by step size, gradually reducing the step size to 1 | $O(n log n)$ | $O(1)$ | Unstable | Medium-scale data sorting | |
| Comparison-based Sorting - Selection Sort | Simple Selection Sort | Select the smallest/largest value in the unsorted sequence in each round and swap it with the first element of the unsorted sequence | $O(n^2)$ | $O(1)$ | Unstable | Small-scale data, space-constrained scenarios |
| Heap Sort | Build a max-heap/min-heap, extract the top element of the heap in each round, and adjust the heap structure | $O(n log n)$ | $O(1)$ | Unstable | Large-scale data, memory-constrained scenarios | |
| Comparison-based Sorting - Merge Sort | Merge Sort | Adopt the divide-and-conquer idea, split the array into subarrays for sorting, and then merge the sorted subarrays | $O(n log n)$ | $O(n)$ | Stable | Large-scale data, external sorting (disk data sorting) |
| Non-comparison-based Sorting | Counting Sort | Count the occurrence frequency of each value and rearrange the data according to the value order | $O(n+k)$ ($k$ is the value range) | $O(n+k)$ | Stable | Sorting integers with a small value range |
| Radix Sort | Sort by each digit of the number, processing digits from least significant to most significant | $O(d(n+r))$ ($d$ is the number of digits, $r$ is the radix) | $O(n+r)$ | Stable | Sorting multi-digit integers, strings |
2. Searching Algorithms
Searching algorithms are used to find target elements from a data set. They can be divided into unordered data searching and ordered data searching based on whether the data is sorted.
| Algorithm Category | Typical Algorithms | Core Idea | Time Complexity | Applicable Scenarios |
|---|---|---|---|---|
| Unordered Data Search | Sequential Search (Linear Search) | Start from the head of the data set, compare elements one by one until the target is found | $O(n)$ | Unordered data, small-scale data |
| Ordered Data Search | Binary Search (Half-interval Search) | Split the sorted array in half, compare the middle element with the target value, and narrow down the search range | $O(log n)$ | Sorted arrays, static data (infrequent additions/deletions) |
| Interpolation Search | Search based on the estimated position of the target value, optimizing binary search for uniformly distributed data scenarios | $O(log log n)$ (ideal case) | Sorted and uniformly distributed data | |
| Structured Data Search | Binary Search Tree Search | Utilize the properties of binary search trees (left subtree < root < right subtree) for recursive or iterative searching | $O(log n)$ (balanced tree) | Dynamic data sets (frequent additions/deletions/queries) |
| Hash Table Lookup | Map the target key to a storage location via a hash function for direct access | $O(1)$ (average case) | High-concurrency queries, caching systems (e.g., Redis) |
3. Divide-and-Conquer Algorithms
The core idea of divide-and-conquer algorithms is "divide and conquer" . A complex large problem is split into several smaller subproblems with the same structure, each subproblem is solved independently, and then the solutions of the subproblems are combined to obtain the solution of the original problem.
Core Steps:
- Divide: Split the original problem into multiple independent subproblems.
- Conquer: Solve each subproblem recursively; if the subproblem size is small enough, solve it directly.
- Combine: Merge the solutions of the subproblems to form the solution of the original problem.
Typical Applications:
- Merge Sort: Split the array into subarrays, sort them, and then merge them.
- Quick Sort: Split the array into two subarrays and sort them recursively.
- Large Number Multiplication: Split large integers into smaller parts for calculation, then merge the results.
- Binary Search: Split the search range into two halves each time to narrow down the lookup space.
4. Dynamic Programming Algorithms
Dynamic programming (DP) algorithms are used to solve multi-stage decision optimization problems. Their core lies in state transition equations and caching subproblem solutions (to avoid redundant calculations) . Unlike divide-and-conquer algorithms, the subproblems in dynamic programming are not independent but have overlapping subproblems and optimal substructure properties.
Core Properties:
- Overlapping Subproblems: Different decision paths will encounter the same subproblems repeatedly.
- Optimal Substructure: The optimal solution of the original problem contains the optimal solutions of the subproblems.
Core Steps:
- Define States: Use variables to represent the solutions of subproblems (e.g., $dp[i]$ represents the optimal solution for the first $i$ elements).
- Derive State Transition Equations: Establish the relationship between the current state and sub-states (e.g., $dp[i] = max(dp[i-1], dp[i-2] + nums[i])$).
- Determine Initial States: Set the solutions of the smallest subproblems (e.g., $dp[0] = 0$).
- Calculate the Final Solution: Derive the solution of the original problem through the state transition equation.
Typical Applications:
- Fibonacci Sequence: Cache intermediate terms to avoid redundant calculations.
- Knapsack Problems: Optimal item selection for 0-1 knapsacks and unbounded knapsacks.
- Longest Common Subsequence (LCS): Find the longest matching sequence between two strings.
- Shortest Path Problems: Calculate the minimum cost of multi-stage paths.
5. Greedy Algorithms
The core idea of greedy algorithms is "deriving global optimality from local optimality" . In each decision step, the locally optimal solution is chosen, with the hope that a series of local optimal choices will eventually lead to a globally optimal solution.
Core Prerequisites: The problem must have the greedy choice property (local optimal choices lead to global optimal solutions) and optimal substructure.
Typical Applications:
- Huffman Coding: Construct an optimal prefix code tree for data compression.
- Activity Selection Problem: Select the maximum number of non-conflicting activities.
- Minimum Spanning Tree: Prim's algorithm (vertex-based greedy) and Kruskal's algorithm (edge-based greedy).
- Shortest Path: Dijkstra's algorithm (single-source shortest path with non-negative edge weights).
Limitations: Greedy algorithms are not applicable to all problems. For example, the 0-1 knapsack problem cannot yield an optimal solution with a greedy algorithm, while the unbounded knapsack problem can under certain conditions.
6. Graph Algorithms
Graph algorithms are used to solve problems related to graph structures, such as graph traversal, path planning, and connectivity analysis. They are core algorithms for scenarios like networks, maps, and social relationships.
| Algorithm Category | Typical Algorithms | Core Idea | Time Complexity | Applicable Scenarios |
|---|---|---|---|---|
| Graph Traversal | Depth-First Search (DFS) | Start from the initial vertex, traverse along one path to the end, then backtrack to explore other paths | $O(V+E)$ ($V$ = number of vertices, $E$ = number of edges) | Graph connectivity detection, topological sorting, path searching |
| Breadth-First Search (BFS) | Start from the initial vertex and traverse all adjacent vertices layer by layer | $O(V+E)$ | Shortest path (unweighted graphs), level traversal, connected component counting | |
| Shortest Path | Dijkstra's Algorithm | Adopt a greedy strategy: select the vertex closest to the source in each step and update the distances of its adjacent vertices | $O(V^2)$ (naive version) / $O(E log V)$ (heap-optimized version) | Single-source shortest path (non-negative edge weights) |
| Floyd-Warshall Algorithm | Adopt a dynamic programming strategy: enumerate intermediate vertices and update the shortest path between any two vertices | $O(V^3)$ | Multi-source shortest path (allowing negative edge weights, no negative weight cycles) | |
| Bellman-Ford Algorithm | Perform relaxation operations to iteratively update vertex distances and detect negative weight cycles | $O(VE)$ | Single-source shortest path (allowing negative edge weights) | |
| Minimum Spanning Tree | Prim's Algorithm | Start from a vertex and gradually add edges with the smallest weight to expand the spanning tree | $O(V^2)$ (naive version) / $O(E log V)$ (heap-optimized version) | Minimum spanning tree for dense graphs |
| Kruskal's Algorithm | Sort edges by weight in ascending order, add edges one by one while avoiding cycles | $O(E log E)$ | Minimum spanning tree for sparse graphs |
7. Other Common Algorithms
- Backtracking Algorithms: Essentially optimized brute-force search, which traverses all possible solutions through a "trial-and-backtrack" approach. If an invalid condition is encountered, backtrack immediately to avoid unnecessary searches. Typical applications: permutation problems, N-Queens problem, subset problems.
- Branch and Bound Algorithms: Similar to backtracking algorithms, but improve search efficiency by "pruning" (setting bounds) to avoid traversing invalid solutions. Typical applications: Traveling Salesman Problem (TSP), integer programming.
- String Matching Algorithms: Used to find the position of a substring in a main string. Typical algorithms include brute-force matching, KMP algorithm (reducing backtracking using a partial match table), and BM algorithm (matching from right to left).
- Machine Learning Algorithms: Belong to the field of artificial intelligence, divided into supervised learning (e.g., linear regression, decision trees, SVM), unsupervised learning (e.g., clustering, dimensionality reduction), and reinforcement learning (e.g., Q-Learning). Their core is to learn patterns from data for prediction or decision-making.
III. Application Scenarios
Algorithms are tools for solving practical problems, and different types of algorithms play key roles in different fields:
Daily Software Development
- Sorting Algorithms: Sorting database query results, sorting list data for display.
- Searching Algorithms: Keyword search within applications, fast lookup of cached data.
- Hash Algorithms: User password encryption, data verification (e.g., MD5, SHA).
Internet and Big Data
- Dynamic Programming: User behavior sequence analysis in recommendation systems.
- Greedy Algorithms: CDN node resource scheduling, priority sorting of task queues.
- Graph Algorithms: Friend recommendation in social networks, logistics path planning in e-commerce platforms.
Artificial Intelligence and Machine Learning
- Deep Learning Algorithms: Convolutional Neural Networks (CNNs) for image recognition, Recurrent Neural Networks (RNNs) for natural language processing.
- Clustering Algorithms: User segmentation, product classification.
- Reinforcement Learning: Decision control for autonomous driving, motion planning for robots.
Embedded and Real-Time Systems
- Sorting Algorithms: Real-time sorting of sensor data (Selection Sort, with low space overhead).
- Searching Algorithms: Fast lookup of device configuration parameters (Binary Search).
- Greedy Algorithms: Real-time task scheduling (prioritizing high-priority tasks).
Scientific Computing and Engineering
- Divide-and-Conquer Algorithms: Large-scale matrix operations, parallel computing of meteorological data.
- Graph Algorithms: Wiring path optimization in circuit design, connectivity analysis of power grids.
- Dynamic Programming: Portfolio optimization and risk assessment in the financial sector.
IV. Summary
Algorithms are the soul of computer science, and their essence is optimal strategies for solving problems. Different types of algorithms have their own applicable scenarios and limitations—divide-and-conquer algorithms excel at splitting complex problems, dynamic programming algorithms are good at handling overlapping subproblems, greedy algorithms are suitable for local optimal decision-making, and graph algorithms are designed for relational network problems.
Mastering algorithms is not about memorizing steps by rote, but understanding their design ideas and applicable conditions. In practical development, it is necessary to select appropriate algorithms based on data structure characteristics and business requirements, balancing time efficiency and space efficiency to build high-performance and reliable systems.