java - 如何计算该算法的Big O？

Question

我想找到method1的大O。

public static void method1(int[] array, int n)
{
    for (int index = 0; index < n - 1; index++)
    {
        int mark = privateMethod1(array, index, n - 1);
        int temp = array[index];
        array[index] = array[mark];
        array[mark] = temp;
    } // end for
} // end method1

public static int privateMethod1(int[] array, int first, int last)
{
    int min = array[first];
    int indexOfMin = first;
    for (int index = first + 1; index <= last; index++)
    {
        if (array[index] < min)
        {
            min = array[index];
            indexOfMin = index;
        } // end if
    } // end for
    return indexOfMin;
} // end privateMethod1

我的想法是我们不需要关心 privateMethod1，这是真的吗？我们在计算 Big O 时是否不需要担心函数调用而只考虑其他因素，例如方法 1 中的赋值操作？

谢谢。

Answer 1

仅在恒定时间内运行的操作，O(1) , 在您分析算法的运行时间时，可以将其视为基本操作；在这种特定情况下，为您的算法找到渐近上界(Big-O 表示法)。 for 中的迭代次数你的方法循环 privateMethod1取决于 index在method1 (它本身取决于 n )以及 n , 并且显然不是在恒定时间内运行。

因此，我们需要包括 privateMethod1在我们对您的算法的 Big-O 分析中。我们将处理所有其他操作，例如赋值和 if语句作为基本操作。

Treated as basic operations in our analysis:

/* in 'method1' */
int temp = array[index];
array[index] = array[mark];
array[mark] = temp;

/* in 'privateMethod1' */
int min = array[first];
int indexOfMin = first;

//...

if (array[index] < min)
{
    min = array[index];
    indexOfMin = index;
}

---

弄清这一点后，您可以使用 Sigma 符号分析算法:外部总和描述了 for循环 method1 ，内部循环描述了 for循环 privateMethod1 , 和 1概括了内部所有基本操作的“成本”for循环。

因此，您的算法的渐近上界 method1是O(n^2) .