LLM 驱动的代码复杂度预测：从静态特征到运行时行为的建模

一、复杂度分析的"纸上谈兵"：大 O 符号与实际性能的断裂

算法题解中常见的复杂度标注（O(n log n)、O(n²)）是渐近分析，描述的是输入规模趋于无穷时的增长趋势。但在实际工程中，常数因子、缓存友好性、分支预测命中率等因素对性能的影响可能比大 O 符号更显著。某团队用 O(n log n) 的归并排序替换了 O(n²) 的插入排序，预期性能提升，结果在 n=1000 的场景下反而变慢——因为插入排序对小数组和部分有序数据有更好的缓存局部性。

LLM 驱动的代码复杂度预测尝试从代码的静态特征推断实际运行时行为，补充大 O 分析无法覆盖的常数因子和硬件效应。

二、LLM 复杂度预测的架构设计

flowchart LR
    CODE[源代码] --> PARSE[AST 解析]
    PARSE --> FEAT[特征提取]
    FEAT --> LLM[LLM 预测]
    LLM --> RESULT[复杂度预测]

    FEAT --> STATIC[静态特征: 循环嵌套/递归深度/数据结构]
    FEAT --> SEMANTIC[语义特征: 算法模式/数据访问模式]

    STATIC --> LLM
    SEMANTIC --> LLM

    RESULT --> BIGO[大 O 复杂度]
    RESULT --> CONST[常数因子估计]
    RESULT --> CACHE[缓存友好性评估]

    style PARSE fill:#eef,stroke:#333
    style LLM fill:#efe,stroke:#333
    style RESULT fill:#fee,stroke:#333

三、复杂度预测引擎的代码实现

import ast
import json
from dataclasses import dataclass, field
from typing import Optional

@dataclass
class ComplexityPrediction:
    """复杂度预测结果"""
    time_complexity: str         # 大 O 符号
    space_complexity: str
    constant_factor: str         # 低/中/高
    cache_friendliness: str      # 好/中/差
    branch_prediction: str       # 好/中/差
    best_case_input: str         # 最优输入描述
    worst_case_input: str        # 最差输入描述
    crossover_point: Optional[int]  # 与 O(n²) 方案的交叉点
    confidence: float            # 预测置信度

@dataclass
class StaticFeatures:
    """静态特征提取结果"""
    loop_depth: int = 0
    has_recursion: bool = False
    recursion_type: str = ""     # linear/tail/tree
    data_structures: list[str] = field(default_factory=list)
    sorting_used: bool = False
    binary_search_used: bool = False
    nested_loops: int = 0
    early_exit: bool = False

class ComplexityPredictor:
    """LLM 驱动的代码复杂度预测引擎"""

    def __init__(self, llm_client):
        self.llm = llm_client

    def predict(self, code: str) -> ComplexityPrediction:
        # 阶段1：提取静态特征
        features = self._extract_features(code)

        # 阶段2：LLM 预测
        prompt = self._build_prompt(code, features)
        response = self.llm.generate(prompt)

        try:
            data = json.loads(response)
            return ComplexityPrediction(
                time_complexity=data.get("time_complexity", "O(?)"),
                space_complexity=data.get("space_complexity", "O(?)"),
                constant_factor=data.get("constant_factor", "中"),
                cache_friendliness=data.get("cache_friendliness", "中"),
                branch_prediction=data.get("branch_prediction", "中"),
                best_case_input=data.get("best_case_input", ""),
                worst_case_input=data.get("worst_case_input", ""),
                crossover_point=data.get("crossover_point"),
                confidence=data.get("confidence", 0.5),
            )
        except json.JSONDecodeError:
            return ComplexityPrediction(
                time_complexity="O(?)", space_complexity="O(?)",
                constant_factor="未知", cache_friendliness="未知",
                branch_prediction="未知", best_case_input="",
                worst_case_input="", confidence=0.0,
            )

    def _extract_features(self, code: str) -> StaticFeatures:
        """从代码中提取静态特征"""
        features = StaticFeatures()
        try:
            tree = ast.parse(code)
            features.loop_depth = self._max_loop_depth(tree)
            features.has_recursion = self._detect_recursion(tree)
            features.data_structures = self._detect_data_structures(tree)
            features.sorting_used = self._detect_sorting(tree)
            features.nested_loops = self._count_nested_loops(tree)
            features.early_exit = self._detect_early_exit(tree)
        except SyntaxError:
            pass
        return features

    def _max_loop_depth(self, tree: ast.AST) -> int:
        """计算最大循环嵌套深度"""
        max_depth = 0
        def visit(node, depth=0):
            nonlocal max_depth
            if isinstance(node, (ast.For, ast.While)):
                depth += 1
                max_depth = max(max_depth, depth)
            for child in ast.iter_child_nodes(node):
                visit(child, depth)
        visit(tree)
        return max_depth

    def _detect_recursion(self, tree: ast.AST) -> bool:
        """检测是否存在递归调用"""
        func_names = set()
        for node in ast.walk(tree):
            if isinstance(node, ast.FunctionDef):
                func_names.add(node.name)

        for node in ast.walk(tree):
            if isinstance(node, ast.Call):
                if isinstance(node.func, ast.Name) and node.func.id in func_names:
                    return True
        return False

    def _detect_data_structures(self, tree: ast.AST) -> list[str]:
        """检测使用的数据结构"""
        structures = set()
        for node in ast.walk(tree):
            if isinstance(node, ast.Name):
                if node.id in ('dict', 'defaultdict', 'Counter'):
                    structures.add('hash_table')
                elif node.id in ('list', 'deque'):
                    structures.add('array')
                elif node.id in ('set', 'frozenset'):
                    structures.add('set')
                elif node.id in ('heapq', 'PriorityQueue'):
                    structures.add('heap')
                elif node.id in ('Tree', 'TreeNode'):
                    structures.add('tree')
        return list(structures)

    def _detect_sorting(self, tree: ast.AST) -> bool:
        for node in ast.walk(tree):
            if isinstance(node, ast.Call):
                if isinstance(node.func, ast.Attribute):
                    if node.func.attr in ('sort', 'sorted'):
                        return True
        return False

    def _count_nested_loops(self, tree: ast.AST) -> int:
        count = 0
        for node in ast.walk(tree):
            if isinstance(node, (ast.For, ast.While)):
                for child in ast.walk(node):
                    if child is not node and isinstance(child, (ast.For, ast.While)):
                        count += 1
                        break
        return count

    def _detect_early_exit(self, tree: ast.AST) -> bool:
        for node in ast.walk(tree):
            if isinstance(node, ast.Break):
                return True
            if isinstance(node, ast.Return) and isinstance(node.value, ast.Constant):
                return True
        return False

    def _build_prompt(self, code: str, features: StaticFeatures) -> str:
        return f"""
请分析以下代码的时间和空间复杂度，并评估实际运行时特征。

代码:

{code}

静态特征:
- 循环嵌套深度: {features.loop_depth}
- 是否递归: {features.has_recursion}
- 数据结构: {features.data_structures}
- 使用排序: {features.sorting_used}
- 嵌套循环数: {features.nested_loops}
- 有提前退出: {features.early_exit}

请输出JSON:
{{
    "time_complexity": "O(?)",
    "space_complexity": "O(?)",
    "constant_factor": "低/中/高（说明理由）",
    "cache_friendliness": "好/中/差（说明理由）",
    "branch_prediction": "好/中/差（说明理由）",
    "best_case_input": "最优输入描述",
    "worst_case_input": "最差输入描述",
    "crossover_point": null或整数（与O(n²)方案的交叉点n值）,
    "confidence": 0.0-1.0
}}
"""

    def compare(self, code_a: str, code_b: str) -> dict:
        """对比两种实现的复杂度"""
        pred_a = self.predict(code_a)
        pred_b = self.predict(code_b)
        return {
            "implementation_a": pred_a,
            "implementation_b": pred_b,
            "recommendation": self._recommend(pred_a, pred_b),
        }

    def _recommend(self, a: ComplexityPrediction, b: ComplexityPrediction) -> str:
        if a.confidence < 0.3 or b.confidence < 0.3:
            return "预测置信度过低，建议通过基准测试验证"
        # 简化推荐逻辑
        return f"方案A复杂度{a.time_complexity}，方案B复杂度{b.time_complexity}，请结合实际数据规模选择"

四、LLM 复杂度预测的 Trade-offs

预测精度有限。LLM 对复杂度的预测基于模式匹配和经验推断，无法替代严格的数学证明。对于非标准算法（如自定义数据结构上的操作），预测可能完全错误。建议将 LLM 预测作为"快速初筛"，关键场景仍需数学推导或基准测试。

静态特征的局限性。AST 分析无法捕获运行时行为——一个看似 O(n) 的循环，如果内部调用了 O(n) 的哈希查找，实际复杂度是 O(n²)。需要结合数据流分析提升特征提取的准确性。

常数因子估计的困难。LLM 对常数因子的估计极其粗略，实际常数因子受编译器优化、CPU 缓存大小、内存分配器等影响，无法从代码静态分析中准确推断。

交叉点的实用价值。crossover_point（两种方案性能交叉的输入规模）对工程选型最有价值，但 LLM 的估计往往偏差较大。建议用 LLM 猜测交叉点范围，再用基准测试精确定位。

五、总结

LLM 驱动的代码复杂度预测通过"静态特征提取 + LLM 语义推理"双引擎，补充了大 O 分析无法覆盖的常数因子、缓存友好性和分支预测等运行时特征。但预测精度有限，不能替代数学证明和基准测试。工程落地的正确姿势是：LLM 预测作为快速初筛和方向指引，数学推导验证渐近复杂度，基准测试确认实际性能。三者的关系是"LLM 猜方向 → 数学证边界 → 测测定性能"。