java - 计算步数和 O 表示法

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

1. 方法一

如果我用n表示数组的长度(其中元素的数量)，这个循环将进行n次迭代。每次迭代都会执行“if”，有时还会执行赋值。无论如何，都会有一个补充来到达表中的下一个项目。所以我们每个元素有 2-3 个操作。复杂度为 O(n)。 (这意味着存在一个自然数p，使得操作次数小于p * n，对于所有 n。在我们的例子中，p = 5 肯定会起作用)。

编辑:为了进一步阐明这个想法:这就像在每次迭代中恰好有 1 个复杂操作最多消耗 p 个时间单位。O(n) 表示算法最多执行 n 个复杂操作。因此，算法的运行时间仅取决于n。

方法2

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

因此，我们在内循环中有 n * n 递增操作，n * n 递减操作执行内部循环，然后执行另一个 n 个增量操作来执行外部循环。这使得复杂度为 O(n^2)。