算法输入输出复杂度与数据结构

更新：2026-10-13；状态：可用；验证范围：教材、原始研究或官方文档核对；概念与方法说明。

从输入、输出、正确性和资源成本理解算法，为生信工具的性能与适用范围打基础。

算法不等于软件名称

算法是一组解决问题的明确步骤；软件实现还包含文件解析、并行、异常处理和版本设置。理解算法时先写输入、输出、目标及限制，例如“输入已排序整数表，输出某值首次可插入的位置”。

输入规模也要定义：样本数n、特征数p、序列长度L或图的节点边数。不能把“数据有1GB”当作所有算法唯一的规模描述。

常见成本

量级	直观增长	生信例子
O(n)	扫一遍	固定每条记录处理成本下的样本计数
O(log n)	不断缩小搜索范围	已排序随机访问数组的二分查找
O(n log n)	常见比较排序	给样本或坐标排序
O(n²)	两两组合	全部样本距离或关系矩阵
O(nm)	两个维度的表	简单序列比对动态规划

Big O通常描述规模增长的上界；不能忽略常数、稀疏性、I/O和实现语言。运行时间短也不表示统计模型正确。

数据结构影响操作成本

数组适合按位置访问；字典/集合适合按键查找和去重；队列适合广度优先遍历；稀疏矩阵只存非零结构，是否节省取决于实际密度。字典不能替代对重复生物学ID的审计，去重也不等于解决重复测量。

先读排序查找与哈希在生信中的应用，再读动态规划与序列比对基础和图与最短路径的生信入门。理论来源：MIT 6.006算法课程。