Neighbor-Joining
基于距离矩阵的系统发育树构建算法，通过迭代地合并最近邻节点来构建无根树。 该方法计算速度快，适合处理大规模数据集，是最常用的距离法建树算法之一。
| Property | Value |
|---|---|
| Purpose | 快速构建系统发育树 |
| Time Complexity | O(n^3) |
| Space Complexity | O(n^2) |
| Year | 1987 |
| Category | Phylogenetics |
Complexity Analysis
- Time Complexity:
O(n^3) - Space Complexity:
O(n^2)
Performance Insight: The time complexity of this algorithm is cubic (O(n³)), only practical for small inputs; heuristic optimizations required at scale. High space complexity; consider Hirschberg-style space-optimized variants for very long sequences.
Note: Complexity analysis is based on theoretical models. Actual runtime is affected by input scale, hardware, and implementation optimizations. Benchmark for your specific workload.
Literature & Implementation
Related Tools
MEGA · PHYLIP · RapidNJ