这个程序的复杂性是什么？

Question

我想分析下面程序的执行时间复杂度。请回答并说明。

private static void printSecondLargest(int[] arr) {
    int length = arr.length, temp;
    for (int i = 0; i < 2; i++) {
        for (int j = i+1; j < length; j++) {
            if(arr[i]<arr[j]) {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
    System.out.println("Second largest is: "+arr[1]);
}

Answer 1

是O(n)其中n表示数组的长度

最内层的循环体：

if(arr[i]<arr[j]) {
    temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

以固定时间运行。

此代码将首先执行 arr.length-1 次，然后执行 arr.length-2 次。即2 * arr.length - 3。因此执行时间与 2n-3 成正比，即 O(n).

Answer 2

外循环会运行两次，内循环会运行s(length-1)和第二次(length-2)

假设长度为N

so it will be 2*((N-1)/2+(N-2/)2)==2*(2n-3)/2

Which is final (2N-3) and in O notation it is O(N)

Answer 3

private static void printSecondLargest(int[] arr) {    
    int length = arr.length, temp;    // **it takes contant time**
    for (int i = 0; i < 2; i++) {     // as loop goes only two step it also takes constant time
        for (int j = i+1; j < length; j++) {   // this loop takes n time if we consider arr length of size n
            if(arr[i]<arr[j]) {
                temp = arr[i];    // it also takes constant time
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
    System.out.println("Second largest is: "+arr[1]);
}

所以根据上面的计算，我们忽略恒定时间并计算所有变化的时间约束，并且根据代码复杂度将为 O(n)。

Answer 4

显然是O(n)。外循环只运行2次，内循环N次。因此，整体复杂度为 O(2*n)。

这个程序的复杂性是什么？

What is the complexity of this program?

java

algorithm

data-structures

big-o

asymptotic-complexity