while 循环函数复杂度有 2 个变量

Question

代码应该找到 2 个数字之间的最大下降（或差异），而较大的数字必须在较小的数字之前（不一定是一个紧挨着另一个）。

我想知道你是否可以帮助我理解代码的复杂性。在这种情况下让我感到困惑的是，考虑最坏的情况（如果我错了请纠正我）我运行通过数组，n 次 j 和 n-1 次 i。它是相加还是相乘？为什么？

O(n+n-1)？或 O(n*(n-1))?

public static int maximalDrop (int[] a)
    {
        int max=0; int i=0; int j=1;
        while (j<a.length && i<a.length-1)
        {
            if (a[i] > a[j])
            {
                int temp = a[i] - a[j];
                if (temp > max)
                {
                    max = temp;
                }
            }
            j++;
            if (j>a.length-1)
            {
                i++;
                j=i+1;
            }
        }
        return max;
    }

Answer 1

此代码的复杂度为 O(n * (n - 1) / 2) 或 O(n^2)。道理很简单，只考虑n = 4的情况，那么while循环每次迭代开始时的(i, j)值如下：

(0, 1), (0, 2), (0, 3)
(1, 2), (1, 3)
(2, 3)

可以看出，复杂度为O(n * (n - 1) / 2)，因为i只有在j从i + 1循环到a.length时才递增。

Answer 2

这段代码的复杂度可以认为是嵌套了2个循环，即O(n^2)

while 循环函数复杂度有 2 个变量

while loop function complexity with 2 variables

java

loops

while-loop

complexity-theory