name: complexity-analyzer description: 代码与算法的自动化Big-O复杂度分析。执行循环结构的静态分析、递归调用树分析、空间复杂度估算以及带详细推导文档的摊还分析。 allowed-tools: Bash, Read, Write, Grep, Glob metadata: author: babysitter-sdk version: “1.0” category: algorithms-optimization skill-id: SK-ALGO-006 priority: high

复杂度分析器

一个专门用于自动化分析算法时间和空间复杂度的技能，提供Big-O符号分析、详细推导和优化建议。

目的

分析代码和算法以确定：

时间复杂度（Big-O、Big-Omega、Big-Theta）
空间复杂度（辅助空间和总空间）
数据结构操作的摊还复杂度
带逐步推理的复杂度推导
优化机会和瓶颈识别

能力

核心分析功能

静态分析
- 循环结构分析（嵌套循环、依赖边界）
- 递归调用树分析
- 函数调用图遍历
- 分支条件影响分析
复杂度类型
- 时间复杂度：最坏、平均和最佳情况分析
- 空间复杂度：栈空间、堆分配、辅助空间
- 摊还分析：聚合方法、会计方法、势能方法
- 递归关系：主定理、代入法
输出格式
- 带详细推导的Big-O符号
- 复杂度对比表
- 可视化复杂度图
- 优化建议

支持的语言

Python（主要）
C++（完全支持）
Java（完全支持）
JavaScript/TypeScript（完全支持）
Go, Rust, C（部分支持）

集成选项

MCP服务器

AST MCP服务器 - 高级代码结构分析：

# 提供AST解析和复杂度分析
npm install -g @angrysky56/ast-mcp-server

代码分析MCP - 自然语言代码探索：

# 带数据流分析的深度代码理解
npm install -g code-analysis-mcp

基于Web的工具

TimeComplexity.ai - AI驱动的运行时复杂度分析
Big-O计算器 - 基于Web的分析

使用方法

分析代码复杂度

# 分析Python函数
complexity-analyzer analyze --file solution.py --function two_sum

# 分析C++代码并带详细推导
complexity-analyzer analyze --file solution.cpp --verbose

# 比较多个实现
complexity-analyzer compare --files impl1.py impl2.py impl3.py

示例分析

输入代码：

def find_pairs(arr, target):
    n = len(arr)
    result = []
    for i in range(n):           # O(n)
        for j in range(i+1, n):  # O(n-i) 次迭代
            if arr[i] + arr[j] == target:
                result.append((i, j))
    return result

分析输出：

时间复杂度：O(n^2)
- 外层循环：n次迭代
- 内层循环：(n-1) + (n-2) + ... + 1 = n(n-1)/2 次迭代
- 总计：O(n^2)

空间复杂度：O(k)，其中k = 找到的配对数量
- result数组随匹配增长
- 最坏情况：如果所有配对都匹配则为O(n^2)

优化建议：
- 使用哈希表实现O(n)时间复杂度
- 以空间换时间：O(n)空间

输出模式

{
  "analysis": {
    "function": "string",
    "language": "string",
    "timeComplexity": {
      "notation": "O(n^2)",
      "bestCase": "O(1)",
      "averageCase": "O(n^2)",
      "worstCase": "O(n^2)",
      "derivation": [
        "步骤1：外层循环运行n次",
        "步骤2：内层循环运行(n-1)、(n-2)、...、1次",
        "步骤3：总计 = 从1到n-1的和 = n(n-1)/2",
        "步骤4：简化为O(n^2)"
      ]
    },
    "spaceComplexity": {
      "notation": "O(n)",
      "auxiliary": "O(n)",
      "total": "O(n)",
      "breakdown": {
        "input": "O(n) - 输入数组",
        "result": "O(k) - 输出配对",
        "variables": "O(1) - 循环计数器"
      }
    },
    "recommendations": [
      {
        "type": "optimization",
        "description": "使用哈希表方法",
        "newComplexity": "O(n)时间，O(n)空间",
        "tradeoff": "以空间换时间"
      }
    ]
  },
  "metadata": {
    "analyzedAt": "ISO8601时间戳",
    "confidence": "high|medium|low"
  }
}

分析模式

循环分析

模式	复杂度	示例
单层循环	O(n)	`for i in range(n)`
嵌套独立循环	O(n*m)	`for i in n: for j in m`
嵌套依赖循环	O(n^2)	`for i in n: for j in range(i)`
对数循环	O(log n)	`while n > 0: n //= 2`
嵌套对数循环	O(n log n)	`for i in n: j=1; while j<n: j*=2`

递归分析

模式	递归关系	复杂度
线性递归	T(n) = T(n-1) + O(1)	O(n)
二分递归	T(n) = T(n/2) + O(1)	O(log n)
分治递归	T(n) = 2T(n/2) + O(n)	O(n log n)
指数递归	T(n) = 2T(n-1) + O(1)	O(2^n)

主定理

对于递归关系 T(n) = aT(n/b) + f(n)：

情况	条件	复杂度
1	f(n) = O(n^c) 其中 c < log_b(a)	O(n^(log_b(a)))
2	f(n) = O(n^c) 其中 c = log_b(a)	O(n^c log n)
3	f(n) = O(n^c) 其中 c > log_b(a)	O(f(n))

与流程集成

此技能增强以下流程：

复杂度优化 - 识别并修复复杂度瓶颈
LeetCode问题求解 - 验证解决方案复杂度
算法实现 - 验证实现效率
代码审查 - 以复杂度为中心的代码审查

常见复杂度类别

复杂度	名称	示例
O(1)	常数复杂度	数组访问、哈希查找
O(log n)	对数复杂度	二分查找
O(n)	线性复杂度	数组遍历
O(n log n)	线性对数复杂度	归并排序、堆排序
O(n^2)	二次复杂度	嵌套循环、冒泡排序
O(n^3)	三次复杂度	矩阵乘法（朴素）
O(2^n)	指数复杂度	子集、递归斐波那契
O(n!)	阶乘复杂度	排列

错误处理

错误	原因	解决方案
`PARSE_ERROR`	无效语法	检查代码语法
`UNSUPPORTED_CONSTRUCT`	复杂控制流	简化或添加注释
`RECURSIVE_DEPTH`	深度递归	提供基本情况提示
`AMBIGUOUS_BOUNDS`	动态循环边界	用约束条件注释

最佳实践

注释约束条件：为准确分析提供变量范围
隔离函数：一次分析一个函数
考虑输入分布：指定平均情况是否与最坏情况不同
审查推导过程：验证逐步推理
用基准测试验证：通过经验验证理论分析

算法复杂度分析器Skill complexity-analyzer

复杂度分析器

目的

能力

核心分析功能

支持的语言

集成选项

MCP服务器

基于Web的工具

使用方法

分析代码复杂度

示例分析

输出模式

分析模式

循环分析

递归分析

主定理

与流程集成

常见复杂度类别

错误处理

最佳实践

参考资料