我对我的答案很肯定，但今天我和朋友讨论说我错了。
我认为这个函数的复杂度是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;
}
这不是作业，只是看起来像作业我们讨论的函数非常类似于气泡排序。无论如何，我已经添加了家庭作业标签。
请帮我确认一下我是否正确。谢谢你的帮助。
最佳答案
复杂性通常是作为函数在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是要排序的部分的长度。