如何计算该算法的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

My thinking is that we need not care about privateMethod1,is this true?

不，你错了。在计算复杂度的同时需要关心其他的函数调用。 privateMethod1 在 O(n) 时间内运行，因为在最坏的情况下 fist 将是 0 而 last 总是 n - 1。所以你的整个循环，即 method1 在 O(n ^ 2) 时间内运行。

Answer 2

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

因此，我们需要在对您的算法进行 Big-O 分析时包含 privateMethod1。我们会将所有其他操作，例如赋值和 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符号分析算法了：外层和描述了method1中的for循环，内层循环描述了for中的循环privateMethod1，而 1 概括了 "the cost" 内部 for 循环中的所有基本操作。

因此，您的算法 method1 的渐近上限为 O(n^2)。

如何计算该算法的Big O？

How to calculate Big O for this algorithm?

java

algorithm

big-o

function-calls