c - 查找数组中最小元素索引的时间复杂度分析——最差、平均和最佳情况

Question

int j = 0;
for(int i = 0; i < n; ++i) {
    while(j < n && arr[i] < arr[j]) {
        j++;
    }
}

这是一个代码，用于查找数组中最小元素(第一次出现)的索引。我说最坏的情况是 O(n2)，最好的情况是 O(n)。

问题 1: 在最坏的情况下，我的内部 while 循环并不总是运行 n 次，在大多数情况下，相对于外部 for 循环，它会运行 1 或 2 次，所以我假设内循环运行 (n-c) 次，其中 c 是某个常数，外循环运行 n 次。我是否正确认为我们的复杂度是 n*(n-c)，即 O(n2)？

在最好的情况下，最小元素在第一个索引处，我的内部循环不会运行任何时间，所以时间复杂度是 O(n)。

问题 2:如何推导出平均情况？

Answer 1

您从 j = 0 开始并且永不递减 j . while 的每次迭代循环增加 j一个，和while循环有条件 j < n , 所以语句 j++最多可以运行 n次，即最坏情况 O(n)。