c++ - 非大 O 复杂性

Question

我对算法复杂度的计算很困惑。对于一项任务，我们被赋予以下功能并要求找到它的复杂性。

int selectkth(int a[], int k, int n) {
    int i, j, mini, tmp;
    for (i = 0; i < k; i++) {
      mini = i;
      for (j = i+1; j < n; j++)
        if (a[j]<a[mini])
          mini = j;
      tmp = a[i];
      a[i] = a[mini];
      a[mini] = tmp;
    }
    return a[k-1];
}

作业本身要求“找到用于在无序整数数组中找到第 k 个最小整数的函数的复杂性。”

此外，我们还被要求编写 f 函数和 g 函数。

据我了解，对于 f 函数，我会在函数中添加所有赋值和操作。我是否在此 f 函数中包含变量 k 或 n？

作为最佳猜测，我会说 f(n) = 6n + 4(n^2)，因为在第一个 for 循环中循环了 6 个操作，然后在嵌套 for 循环中循环了 4 个操作。

为了进一步理解，这个函数的Big O复杂度是O(n^2)吗？我这么说是因为有一个嵌套的 for 循环，这意味着每次都要遍历每个项目的最坏情况。

如果我没有说清楚，我深表歉意。我对它的工作原理感到很困惑。

Answer 1

简单分析一下:

外循环正在进行 k 次迭代。

Inter 循环正在执行 n-1 次迭代，但它执行了 k 次。

所以我们有 O(k*(n-1)) = O(kn-k)由于 k 可以等于 n(我们可以要求数组中的第 n 个最小整数)表达式变为 O(n*n-n) = O( n^2-n) = O(n^2).

有关大 O 表示法的更多帮助，请查看:http://web.mit.edu/16.070/www/lecture/big_o.pdf