c - 这个函数的时间复杂度

Question

我很确定我的答案，但今天和我的 friend 讨论，他说我错了。

我认为此函数的复杂度在平均和最坏情况下为 O(n^2)，在最佳情况下为 O(n)。对吧？

现在当 k 不是数组长度时会发生什么？ k 是您要排序的元素数(而不是整个数组)。

最好和最坏情况下是 O(nk) 还是最好情况下是 O(n)？

这是我的代码:

#include <stdio.h>

void bubblesort(int *arr, int k)
{
    // k is the number of item of array you want to sort
    // e.g. arr[] = { 4,15,7,1,19} with k as 3 will give
    // {4,7,15,1,19} , only first k elements are sorted
  int i=k, j=0;
  char test=1;
  while (i && test)
  {
    test = 0;
    --i;
    for (j=0 ; j<i; ++j)
    {
      if ((arr[j]) > (arr[j+1]))
      {
          // swap 
          int temp = arr[j];
          arr[j]=arr[j+1];
          arr[j+1]=temp;
        test=1;
      }

    }  // end for loop

  } // end while loop
}

int main()
{

    int i =0;
    int arr[] = { 89,11,15,13,12,10,55};
    int n = sizeof(arr)/sizeof(arr[0]);

    bubblesort(arr,n-3);
    for (i=0;i<n;i++)
    {
        printf("%d ",arr[i]);
    }
    return 0;
}

附言这不是家庭作业，只是看起来像一个。我们讨论的功能与冒泡排序非常相似。无论如何，我已经添加了作业标签。

请帮我确认一下我说的对不对。感谢您的帮助。

Answer 1

复杂度通常作为 n(或 N)上的函数给出，例如 O(n)、O(n*n)、...

关于您的代码，复杂性如您所述。最好情况下为 O(n)，最坏情况下为 O(n*n)。

在你的情况下可能导致误解的是你有一个变量 n (数组的长度)和一个变量 k (数组中要排序的部分的长度)。当然，排序的复杂性不取决于数组的长度，而是取决于要排序的部分的长度。因此，对于您的变量，复杂度为 O(k) 或 O(k*k)。但是由于通常复杂性表示法超过 n，您会说 O(n) 或 O(n*n)，其中 n 是要排序的部分的长度。