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

Question

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

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
}

Answer 1

让我们计算一下操作数:

• 外层循环运行 n-1 次

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

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

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

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