gpt4 book ai didi

c - 求冒泡排序的时间复杂度?

转载 作者:行者123 更新时间:2023-11-30 21:00:29 25 4
gpt4 key购买 nike

谁能帮我计算以下冒泡排序函数的时间复杂度?我真的很难做到这一点。如果有人能在这方面帮助我,那将非常有帮助。下面是我的代码:

void bubble_sort ( int n )
{
int i, j, k, temp ;
struct link *p, *q ;
k = n;
for ( i = 0 ; i < n - 1 ; i++, k-- )
{
p = head ;//Sorting the linked list in descending order for displaying
q = p ->next ;

for ( j = 1 ; j < k ; j++ )
{
if ( p -> freq < q -> freq )//checking frequencies for sorting
{
temp = p ->freq ;
p -> freq = q -> freq ;
q -> freq = temp ;
}
p = p -> next ;
q = q -> next ;
}
}//Sorted linked list
}

最佳答案

让我们计算一下操作数:

  • 外层循环运行 n-1

  • 对于每次迭代,内部循环运行 n - i - 1 次。

  • 大部分代码位于嵌套循环内:一次比较、一次交换操作和 2 次指针修改:O(1) 时间。

操作总数为(n * (n - 1)/2) * O(1)

因此上述代码的时间复杂度为O(n2)

关于c - 求冒泡排序的时间复杂度?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41090847/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com