Algorithmic Guide: From Zero Mastering Algorithm Design and Core Logic of Application
Algorithm Basic Cognition and Complexity Analysis
Basic Concepts of Algorithms
- Definition and Core Characteristics of Algorithms: Finiteness, Determinism, Feasibility, Input, Output
- The Difference and Connection Between Algorithms and Programs: An algorithm is a logical thought, while a program is the code implementation of that algorithm.
- Classification of Algorithms: By Function (Sorting, Searching, Graph Processing) and by Design Paradigm (Greedy, Divide-and-Conquer, etc.)
Algorithm Complexity Analysis
- Time Complexity: Big O Notation Definition and Calculation Methods (Nested Loops, Recursive Scenarios)
- Space Complexity: An Analysis and Calculation of Auxiliary Space Used
- Common Complexity Levels and Efficiency Comparison: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ)
- Practical Complexity Analysis: Deriving the Complexity of Classic Algorithms (Bubble Sort, Binary Search)
Correctness and Optimization Principles of Algorithms
- Proof Strategies for Algorithm Correctness: Simple Applications of Induction and Proof by Contradiction
- Core Directions for Algorithm Optimization: Reducing Time Complexity, Minimizing Space Usage, and Enhancing Code Readability
- Algorithm Learning Methods: From Imitation to Innovation (Understanding → Implementation → Optimization → Expansion)
Sorting and Searching Algorithms
Basic Concepts and Description of Processes - 2
- Basic Concepts of Sorting: The Difference Between Internal and External Sorting
- Insertion Sort: Principles and Performance of Direct Insertion Sort and Shellsort
- Exchange Sort: The Divide and Conquer Approach and Optimizations of Bubble Sort and Quick Sort
- Selection Sort: Implementation Logic of Simple Selection Sort and Heap Sort
- Merge Sort: A Stable Sorting Algorithm Based on Divide and Conquer
- Radix Sort: A Distribution and Collection Sorting Method Based on Keywords
- Performance Comparison of Various Sorting Algorithms and Selection Recommendations
Fundamentals of Search Algorithms
Basic Algorithm Ideas: Divide and Conquer and Backtracking
Divide and Conquer Algorithm
- Design of Divide and Conquer Algorithms: Divide and Conquer (Split → Solve → Merge)
- Conditions for Applying Divide and Conquer Algorithms: Problem Divisibility, Independent Subproblems, and Merging of Subproblem Solutions
- Classic Divide and Conquer Algorithm Examples: Merge Sort, Quick Sort, Binary Search, Big Number Multiplication
- Time Complexity Analysis of Divide and Conquer Algorithms: A Simple Application of the Master Theorem (Recursive Equation)
Backtracking algorithm
- The Core Idea of Backtracking Algorithms: Exploratory Search + Pruning (Backtrack if Conditions are Not Met)
- Implementing Backtracking Algorithms: Recursive Backtracking, Iterative Backtracking (Stack Simulation)
- Optimizing Backtracking Algorithms: Pruning Strategies (Feasibility Pruning, Optimality Pruning)
- Classic Backtracking Algorithm Examples: Permutations, Combination Sum, N-Queens Problem, and Subset Problem
Divide and Conquer vs. Backtracking: Differences and Connections
Advanced Algorithm Ideas: Dynamic Programming
Dynamic Programming Fundamentals
- The Core Idea of Dynamic Programming: Overlapping Subproblems + Optimal Substructure (Avoiding Redundant Computation)
- The Difference Between Dynamic Programming, Divide and Conquer, and Greedy Algorithms: Subproblem Overlap is the Key Distinction
- Steps for Solving Dynamic Programming Problems: Define State → Derive the State Transition Equation → Initialization → Tabulation Calculation
Classic Dynamic Programming Problems (Fundamentals)
Classic Dynamic Programming Problems (Advanced Level)
Graph Algorithms
Graph Traversal and Basic Operations
- Depth-First Search (DFS): Recursive and Non-Recursive Implementations & Applications (Connected Components, Cycle Detection)
- Breadth-First Search (BFS): Queue Implementation and Applications (Shortest Path, Level Order Traversal)
- Graph Representation: Adjacency Matrix, Adjacency List, and Algorithm Suitability
Shortest Path Algorithm
- Single-Source Shortest Path: Dijkstra's Algorithm (Without Negative Edge Weights)
- Single Source Shortest Path: Bellman-Ford Algorithm (Handling Negative Edge Weights, Detecting Negative Cycles)
- Multi-Source Shortest Paths: The Principles and Applications of the Floyd-Warshall Algorithm
- Shortest Path Algorithm Selection: Choosing Based on Graph Type (Positive/Negative Weights, Dense/Sparse)
Other Classic Algorithms for Graphs
String Algorithms
String Basic Operations and Matching
Advanced String Processing Algorithms
Basic Algorithm Ideas: Enumeration and Greedy Algorithms
Overview of Lexical Analysis
- Design Considerations for the Enumeration Algorithm: Exhausting All Possible Solutions and Validating Their Effectiveness
- Applicable Scenarios for Enumeration Algorithms: Situations with Small Problem Sizes and Finite Solution Spaces
- Optimization Techniques for Enumeration Algorithms: Pruning (Eliminating Invalid Solutions) and Reducing the Search Space
- Practical Algorithms: The Chicken and Money Problem, Lilium Number Search
Greedy Algorithm
- The Core Idea of the Greedy Algorithm: Local Optima → Global Optimum Decision Logic
- Applicability of Greedy Algorithms: Problem Possessing a Greedy Choice Property and Optimal Substructure
- Limitations of the Greedy Algorithm: Unable to Solve All Optimization Problems (Such as Ordinary Scenarios of the Knapsack Problem)
- Classic Greedy Algorithm Examples: Activity Selection, Huffman Coding, Minimum Spanning Tree (Prim/Kruskal)
Advanced Data Structures and Algorithm Optimization
Advanced Data Structures and Algorithmic Applications
- Heaps: Implementation of Max Heap / Min Heap, Heap Sort, and Top-K Problem Solving
- Disjoint Set Union: Path Compression + Rank/Union Optimization and Connected Component Problems
- Balanced Binary Trees (AVL Trees, Red-Black Trees)
- Segment Trees: Principles and Implementation of Range Queries and Range Updates (Sum, Minimum/Maximum)
Algorithm Optimization Techniques
- Prefix Sums and Differences: One-Dimensional/Two-Dimensional Prefix Sums, Difference Arrays (for Fast Range Increment/Decrement Handling)
- Two Pointers: Forward Pointer, Backward Pointer (Optimization for Array/String Problems)
- Sliding Window: Solving Substring/Subarray Problems in Linear Time (e.g., Longest Unique Substring)
- Memoization Search: Optimizing Recursive Problem Repetitions (Recursive Implementation of Dynamic Programming)
Algorithm Practical Application and Comprehensive Use
- Array/Linked List Problems: Circular Linked List Detection, Linked List Sorting, Array Rotation
- High-Frequency Interview Algorithms: Two Sum, Three Sum, Rain Water, Maximum Subarray Sum
- Expanding Algorithmic Thinking: Combining Multiple Algorithms to Solve Complex Problems (e.g., Dynamic Programming + Greedy Combination)