java - Big O 分析中方法调用和返回语句的成本是多少？

Question

我刚刚开始进行算法分析，当涉及到方法调用和返回语句的成本时，似乎出现了歧义。有些来源对它们的计数与其他来源不同，所以我希望对此有所澄清。采用我编写的算法来计算最大子数组(取自伪代码):

public static int maxSubFastest(int[] array)
    {
        //index variable t
        int t;
        Integer[] M = new Integer[array.length];
        //initial prefix maximum
        M[0] = 0;

        for (t = 1; t < array.length; t++)
        {
            M[t] = max(0, M[t - 1] + array[t]);
        }
        //maximum found so far
        int m = 0;
        for (t = 1; t < array.length; t++)
        {
            m = max(m, M[t]);
        }
        return m;
    }

通过方法调用:

//method to calculate the max for maxSubFastest
    public static int max(int a, int b)
    {
        return a > b ? a:b;
    }

我对这个算法的初步分析给了我:

T(n) = 8(n - 1) + 9

= 8n - 8 + 9

= 8n + 1 = O(n)

我知道最后的结果还是O(n)，但是这里，我算了一下:

M[t] = max(0, M[t - 1] + array[t]);

作为成本 2(n - 1)，(n - 1) 用于赋值，(n - 1) 用于方法调用。我没有算最后的return语句。

这看起来是一个相当准确的分析吗？我是否应该将方法调用计算为超过 cost 1*(n - 1) 以及最后的 return 语句？

Answer 1

长话短说

调用一个方法是O(1)，执行方法体依赖于方法，从方法返回是O(1)。所以总的来说，重要的是方法体的 Big-O(只要它不是或多或少不可能的 O(0))。

详细解释

方法调用(从调用方的角度来看)由三部分组成:

• 将控制权和参数转移到被调用的方法。由于 Java 在将实例或数组内容作为参数传递之前不会复制实例或数组内容，因此对于每个参数来说这是恒定时间，因此对于固定参数列表来说，整体时间也是恒定时间。所以这里我们有 O(1)。如果您有复杂的表达式作为参数传递，请在方法调用之外计算它们。
• 执行方法的主体(包括任何复杂的返回表达式)。这当然取决于方法。您的 max(a,b) 方法没有循环，因此它也是常数时间:O(1)。
• 返回一些值。再次说明，Java 不执行可能导致可变时间的内容复制，因此它是常数时间:O(1)。

您可能会问，将控制权转移到无参数方法所花费的时间是否与具有 10 个参数的方法所花费的时间相同。假设它是 1 用于准备和执行方法调用，1 用于传递单个参数。然后第一种情况得到 1，第二种情况得到 11。但是对于Big-O，11和1是一样的(都是常量)，所以结果是O(1)。