java计数步骤和操作

Question

这两种方法各有多少个步骤？当我使用这两种方法中最坏的情况时，我如何计算它们？我读过大量关于如何计算O形符号（本例中最小的O形符号量）的文章，但不知道它是如何工作的。我知道程序的功能，但有人能帮我计算最坏情况下的步数和O表示法吗

static int methode1(int[] arr) { 
    int min = 100; 
    int minidx = 0; 
    for(int i = 0; i<arr.length; i++) { 
        if(arr[i]<min) { 
            minidx = i; 
        } 
    } 
    return minidx; 
}

static int methode2(int n) { 
    int count = 2; 
    for(int i = 1; i<=n; i++) { 
        for(int j=n; j>i; j--) { 
            count++; 
        } 
    }
    return count; 
}

Answer 1

首先，对于两种方法都不需要考虑最坏的情况，因为这两种方法都没有条件退出。p>

下一个，第一个，当你寻找数组中的最小元素（很可能没有排序）时，你必须逐字检查每个元素以找到最小的元素，因此复杂性将是^ {CD1>}。

关于第二个循环，您有两个嵌套循环，对于外部循环的第一次迭代，您在内部循环中进行n迭代，对于第二次迭代，您在进行n - 1，等等。。。例如

n, n - 1, n - 2, ..., 1

它变成了算术级数，加起来是n*(n+1)/2，在大O表示法中是O(n^2)

Answer 2

1. 方法1

如果我用n表示数组的长度（数组中的元素数）， 这个循环将进行n迭代。在每次迭代中，都会执行一个“if”，有时还会执行一个赋值。在任何情况下，都会有一个附加项进入表中的下一项。每个元素有2-3个操作。复杂性为O（n）。（这意味着存在一个自然数p，因此对于所有n，操作数小于p*n。在我们的例子中，像p=5这样的操作肯定会起作用）

编辑：进一步澄清一点：这就像在每次迭代中都有一个复杂的操作，最多消耗p时间单位。 O（n）意味着算法最多执行这些复杂操作中的n。因此，算法的运行时间仅取决于n

1. 方法2

在这种情况下，有一个循环从1计数到n。这些是n操作。对于这些步骤中的每一步，都有另一个从n到1的循环计数，这也是n操作。在第二个循环中，只有一个增量操作

因此，我们在内环中有n*n递增操作，n*n递减操作来做内环，还有另一个n递增操作来做外环。这使得O变得复杂（n^2）

Answer 3

它将是method1-O（arr.length），method2-O（n^2）

方法中有for个循环。可以计算循环中代码的执行次数。在第二种情况下，有一个循环嵌套在另一个循环中。在这种情况下，执行次数等于第一个循环中的执行次数，乘以第二个循环中的执行次数