← 知识手册目录算法方法 · GESP 3 / 4 / 5 / 6 / 7 / 8 级相关跳到完整速查 ↓

PYTHON KNOWLEDGE · 12

算法、复杂度与解题验证

把题意转成输入、状态、规则与输出，用正确性和复杂度共同评价解法。

GESP 3 级GESP 4 级GESP 5 级GESP 6 级GESP 7 级GESP 8 级

01 · FORMAL DEFINITION

正式定义

算法是解决一类问题的有限、明确步骤。正确性说明算法对所有满足前置条件的输入都得到规定结果；时间和空间复杂度描述输入规模增长时资源使用的增长量级。

02 · MUST KNOW

学完这一章，必须说清楚的规则

  1. 01

    先明确输入规模 n、数据范围、目标和允许误差，再选择数据结构与算法。

  2. 02

    O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ) 表示增长量级，不是精确运行秒数。

  3. 03

    顺序代码复杂度取较大项，嵌套循环常相乘，二分每步把范围缩小一半。

  4. 04

    正确性可用循环不变量、数学归纳、交换论证、反证或状态定义来说明。

  5. 05

    样例只验证少量输入；必须自己设计边界、极端、重复、有序/逆序和无解数据。

  6. 06

    优化前先得到正确基线并测量瓶颈，不为小数据盲目增加复杂实现。

03 · RUNNABLE EXAMPLE

可运行示例与因果解释

PYTHON
def binary_search(values, target):
    left, right = 0, len(values) - 1
    while left <= right:
        mid = (left + right) // 2
        if values[mid] == target:
            return mid
        if values[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

COMMON PITFALLS

常见误区

  • 只看样例通过就宣称正确
  • 不看数据范围使用 O(n²)
  • 二分区间开闭混用
  • 把 O(n) 当成永远比 O(log n) 慢固定倍数

SCOPE & BOUNDARIES

适用边界

  • 复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
  • 考场策略、课程完成度和算法能力是不同证据，任何单项都不能保证考级通过。