java - 时间复杂度方法调用计算

Question

在计算方法调用的时间复杂度时，我是否也必须考虑方法的复杂度或只将复杂度视为常数时间？谢谢，谢谢

Answer 1

您必须考虑方法的复杂性。

这里有一个简单的例子来说明这一点：假设你有一个算法，可以对矩阵的所有元素求和；你可以做 ：

sum = 0
for (i = 0; i < m.M; ++i)
    for (j = 0; j < m.N; ++j)
        sum += m[i, j];

或者 ：

sum = 0
for (i = 0; i < m.M; ++i)
    sum += sumRow(m, i);

使用 sumRow：

for (j = 0; j < m.N; ++j)
    sum += m[i, j];
return sum

如您所见，您不能将 sumRow 函数视为具有恒定复杂性，因为它的执行时间取决于问题的维度。

但是，如果该方法不依赖于您认为它在恒定时间内执行的任何维度。

例如，您可以在求和之前预测值：

sum = 0
for (i = 0; i < m.M; ++i)
    for (j = 0; j < m.N; ++j)
        sum += project(m[i, j]);

然后您将项目视为常数时间，因为它仅取决于标量值而不是矩阵的维度。