什么是输入大小

Question

当我即将了解一些算法时，我对输入大小到底是什么感到困惑。

例如旅行推销员问题动态规划实现需要O(2ⁿ×n²)

Kruskal 的算法采用 O（E日志V）。虽然两者都是图形问题，但为什么 TSP 输入大小是顶点数 n 而在 Kruskal 算法中输入大小是边和顶点。

如何准确知道什么可以作为输入大小？

Answer 1

您可以根据自己喜欢的任何变量来说明算法的复杂性。

您通常应该选择它们来清楚地传达有关算法 运行 时间的有用信息。