📚 Computer Science Fundamentals: Algorithm Principles and Complexity Analysis | 计算机基础：算法原理与复杂度分析
An algorithm is a finite, well-defined sequence of steps used to solve a specific problem. Understanding how algorithms work and how to measure their efficiency is one of the most important foundations in computer science.
算法是用于解决特定问题的有限、明确定义的步骤序列。理解算法如何工作以及如何衡量其效率，是计算机科学最重要的基础之一。
1. What Is an Algorithm? | 什么是算法
An algorithm takes an input, performs a series of clear operations, and produces an output. It must be unambiguous, executable, finite, and general enough to handle all valid inputs of the same type.
算法接收输入，执行一系列清晰的操作，并产生输出。它必须无歧义、可执行、有限，并且具有足够的通用性以处理同一类型的所有有效输入。
Unambiguous: each step has exactly one meaning, with no confusion.
无歧义：每一步只有一种含义，不产生混淆。
Finite: the algorithm stops after a finite number of steps.
有限性：算法在有限步数后停止。
Effective: every operation can be carried out in practice.
有效性：每个操作都可以在实践中完成。
Input/Output: it must accept data and produce a result.
输入/输出：它必须接收数据并产生结果。
A recipe for baking a cake is a useful analogy: if any step is vague, or the process never ends, the recipe fails. Similarly, an algorithm must be precise and terminating.
烘焙蛋糕的配方是一个有用的类比：如果任何步骤不明确，或者过程永不结束，配方就失败了。同样，算法必须精确并且能够终止。
2. Why Complexity Analysis Matters | 为什么复杂度分析很重要
Two algorithms can both solve a problem correctly, but one may run in microseconds while the other takes centuries for large inputs. Complexity analysis gives us a scientific way to compare algorithms without running them on every possible machine.
两个算法都可以正确解决问题，但一个可能在微秒内运行完成，而另一个在处理大规模输入时可能需要数百年。复杂度分析为我们提供了一种科学方法，无需在每台机器上运行即可比较算法。
Complexity is usually expressed as a function of input size n. We focus on how the running time or memory usage grows as n increases, rather than on exact clock time, because hardware and programming languages vary.
复杂度通常表示为输入规模 n 的函数。我们关注运行时间或内存使用如何随 n 的增大而增长，而不是精确的时钟时间，因为硬件和编程语言各不相同。
3. Big-O Notation | 大 O 记号
Big-O notation describes the upper bound of an algorithm's growth rate. It gives a worst-case, asymptotic measure of time or space complexity in the simplest possible form.
大 O 记号描述算法增长率的渐近上界。它给出了时间或空间复杂度在最坏情况下的渐近度量，并以最简形式表示。
f(n) = O(g(n)) means f(n) grows no faster than g(n), up to a constant factor.
f(n) = O(g(n)) 表示 f(n) 的增长速度不超过 g(n)，至多相差一个常数因子。
Common classes from slowest to fastest growth: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ).
常见复杂度类别从慢到快：O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ)。
4. Common Complexity Classes | 常见复杂度类别
| Class | Name | Example |
| O(1) | Constant | Array index access |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Simple loop over array |
| O(n log n) | Linearithmic | Mergesort, Quicksort average |
| O(n²) | Quadratic | Nested loops, Bubble sort |
| O(2ⁿ) | Exponential | Recursive subset generation |
For example, accessing the third element of an array is O(1), because the address is calculated directly. Searching for a value in an unsorted array is O(n) in the worst case, since we may need to check every element.
例如，访问数组的第三个元素是 O(1)，因为地址可以直接计算。在未排序数组中查找一个值，最坏情况下是 O(n)，因为可能需要检查每一个元素。
5. Time Complexity vs Space Complexity | 时间复杂度与空间复杂度
Time complexity measures the number of basic operations an algorithm executes. Space complexity measures the amount of extra memory it uses beyond the input.
时间复杂度衡量算法执行的基本操作数量。空间复杂度衡量算法在输入之外使用的额外内存量。
Sometimes we can trade space for time, for example by storing precomputed results in a hash table to make future lookups O(1).
有时我们可以用空间换取时间，例如将预先计算的结果存储在哈希表中，使后续查找为 O(1)。
Consider the Fibonacci sequence. A naive recursive implementation has exponential time complexity, while an iterative version with an array runs in O(n) time and uses O(n) space. Even better, using just two variables reduces space to O(1).
考虑斐波那契数列。朴素递归实现具有指数时间复杂度，而带数组的迭代版本运行时间为 O(n)，空间为 O(n)。更好的是，只用两个变量可以将空间降低到 O(1)。
6. Analyzing Loops | 分析循环
Loops are the most common source of time complexity. A single loop that runs n times has O(n) complexity if each iteration does constant work.
循环是时间复杂度最常见的来源。如果每次迭代做常数工作，运行 n 次的单个循环具有 O(n) 复杂度。
A nested loop where both loops run n times gives O(n²), because the inner loop executes n times for each of the n outer iterations.
两个都运行 n 次的嵌套循环给出 O(n²)，因为对于 n 次外层迭代中的每一次，内层循环都执行 n 次。
Constant work inside loop: O(n)
循环内常数工作：O(n)
Inner loop depends on outer loop: sum 1 + 2 + ... + n = n(n+1)/2, which is O(n²)
内层循环次数依赖外层循环：和 1 + 2 + ... + n = n(n+1)/2，即 O(n²)
Loop variable doubles each step: while (i < n) i *= 2 → O(log n)
循环变量每次加倍：while (i < n) i *= 2 → O(log n)
Be careful: a nested loop is not always O(n²). If the inner loop runs a constant number of times, the total is still O(n).
注意：嵌套循环不总是 O(n²)。如果内层循环运行常数次，总复杂度仍然是 O(n)。
7. Recursion and Recurrence Relations | 递归与递推关系
Recursion occurs when a function calls itself on a smaller input. To analyze recursive algorithms, we write a recurrence relation that describes T(n) in terms of T(n/k).
递归发生在函数对更小的输入调用自身时。为了分析递归算法，我们写出递推关系，用 T(n/k) 的形式描述 T(n)。
Mergesort is a classic example: it splits the array in half, sorts each half recursively, and merges the two sorted halves in O(n) time.
归并排序是一个经典例子：它将数组分成两半，递归排序每一半，然后以 O(n) 时间合并两个有序部分。
T(n) = 2T(n/2) + O(n) → T(n) = O(n log n)
T(n) = 2T(n/2) + O(n) → T(n) = O(n log n)
nly O(1) extra work per level, so its recurrence is T(n) = T(n/2) + O(1), giving O(log n).
二分查找将问题规模减半，但每层只执行 O(1) 额外工作，因此其递推为 T(n) = T(n/2) + O(1)，得到 O(log n)。
8. Best, Average, and Worst Cases | 最好、平均与最坏情况
An algorithm's running time can vary greatly depending on the input. Quicksort may run in O(n log n) for random data, but in O(n²) for already sorted data when a naive pivot is chosen.
算法的运行时间可能因输入而有很大差异。对于随机数据，快速排序可能在 O(n log n) 时间内运行，但当选择朴素的基准元素且数据已经有序时，可能退化为 O(n²)。
| Case | Meaning | Quicksort Example |
| Worst case | Maximum time over all inputs of size n | O(n²) |
| Average case | Expected time over random inputs | O(n log n) |
| Best case | Minimum time for the most favorable input | O(n log n) |
We usually focus on the worst case because it gives a guarantee of performance that is independent of assumptions about input distribution.
我们通常关注最坏情况，因为它给出了与输入分布假设无关的性能保证。
9. Algorithm Design Strategies | 算法设计策略
Several general strategies help us design efficient algorithms for a wide range of problems.
几种通用策略帮助我们为各种问题设计高效算法。
Divide and conquer: split the problem, solve subproblems, combine results.
分治法：拆分问题，解决子问题，合并结果。
Greedy strategy: make the locally optimal choice at each step.
贪心策略：每一步做出局部最优选择。
Dynamic programming: store solutions to overlapping subproblems.
动态规划：存储重叠子问题的解。
Backtracking: explore choices and backtrack when a path fails.
回溯法：探索选择，当路径失败时回溯。
Mergesort and binary search are divide-and-conquer algorithms. Dijkstra's shortest path algorithm is greedy. The knapsack problem is often solved with dynamic programming.
归并排序和二分查找是分治算法。Dijkstra 最短路径算法是贪心的。背包问题通常用动态规划解决。
10. Comparing Algorithms: A Practical Example | 比较算法：实际例子
Consider searching for a target value in a sorted array. A linear search checks each element one by one, so it runs in O(n) time. Binary search repeatedly halves the search range, running in O(log n) time.
考虑在有序数组中查找目标值。线性搜索逐个检查元素，因此运行时间为 O(n)。二分查找反复将搜索范围减半，运行时间为 O(log n)。
e worst case. Binary search needs only about 20 comparisons, because log₂(1,000,000) ≈ 20.
对于一百万元素的数组，线性搜索最坏可能需要一百万次比较。二分查找大约只需要 20 次比较，因为 log₂(1,000,000) ≈ 20。
This dramatic difference shows why choosing the right algorithm often matters more than choosing a faster computer.
这种巨大差异表明，选择正确的算法通常比选择更快的计算机更重要。
11. Common Pitfalls in Complexity Analysis | 复杂度分析中的常见误区
Students often make mistakes when analyzing algorithms. Here are a few pitfalls to avoid.
学生在分析算法时经常会犯错误。以下是一些需要避免的误区。
Treating every nested loop as O(n²). Check whether the inner loop's bound depends on n.
把每个嵌套循环都当作 O(n²)。要检查内层循环的边界是否依赖于 n。
Forgetting that O(1) operations inside a loop multiply by the number of iterations.
忘记循环内的 O(1) 操作需要乘上迭代次数。
Ignoring the cost of function calls in recursive algorithms.
忽略递归算法中函数调用的成本。
Using exact timing measurements instead of asymptotic growth when comparing algorithms.
比较算法时使用精确计时测量，而不是渐近增长率。
Always simplify constants and lower-order terms: 3n² + 5n + 7 is O(n²), because n² dominates as n becomes large.
始终简化常数和低阶项：3n² + 5n + 7 是 O(n²)，因为当 n 变大时 n² 占主导地位。
12. Summary and Exam Tips | 总结与考试提示
Complexity analysis is a central theme in computer science exams. You should be able to determine the Big-O complexity of loops, recursion, and common algorithms such as sorting and searching.
复杂度分析是计算机科学考试的核心主题。你应该能够确定循环、递归以及排序和搜索等常见算法的 Big-O 复杂度。
Key formulas to remember: binary search is O(log n), mergesort is O(n log n), bubble sort and selection sort are O(n²), and simple linear scans are O(n).
需要记住的关键结论：二分查找是 O(log n)，归并排序是 O(n log n)，冒泡排序和选择排序是 O(n²)，简单线性扫描是 O(n)。
When writing answers, always state whether you are analyzing time or space complexity, and explain the worst case explicitly. Show your recurrence relation for recursive algorithms.
写答案时，始终说明你分析的是时间复杂度还是空间复杂度，并明确解释最坏情况。对于递归算法，要展示递推关系。
Finally, practice by tracing algorithms on small arrays and counting operations carefully. This skill will make complexity analysis intuitive and automatic.
最后，通过在小型数组上跟踪算法并仔细计算操作数来练习。这项技能将使复杂度分析变得直观而自然。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图