java - 对 Bubblesort 算法进行正确的运行时分析

Question

嘿，我对 Bubblesort 进行了运行时分析，我想问你是否有任何错误，因为我在某个时候不确定

这里是算法的摘录:

boolean sorted = false;
        while(!sorted)
        {
            int a = 0;
            int b = 1;
            sorted = true;
            while(a < sortArray.length  && b < sortArray.length)
            {
                if(sortArray[a].getWertigkeit() < sortArray[b].getWertigkeit())
                {
                    Karte tmp1 = sortArray[a];
                    Karte tmp2 = sortArray[b];
                    sortArray[a] = tmp2;
                    sortArray[b] = tmp1;
                    sorted = false;
                }

                a++;
                b++;
            }
        }

所以我得到的问题是在第一个 while 循环中，我按如下方式解决了它:

• 最好的情况:在最好的情况下，sorted 永远不会被设置回 false(通过 if(..){..})所以它只通过循环一次；因此，如果我没记错的话，运行时间是 2*2n*1 = 4n => O(n) 对于最佳情况；

• 最坏的情况:据我所知，在最坏的情况下，每次循环开始时变量 sorted 都会设置为 false，因此它需要另一次“n”次比较，因此运行时间应该是:n*2n*1 = 2n^2 => O(n^2)

我真的不确定我对 while(!sorted) 的想法是否正确，或者运行时是否有意义(因为大 o 符号看起来不错，但我不确定精确的运行时)

我真的希望我的问题是相关的，我期待收到您的来信。

谢谢

Answer 1

您对 O(n) 的最佳运行时间的分析是正确的。干得好!

对于最坏的情况，您需要更精确一些。你是对的，每次重置标志时，你都必须再次遍历数组以使其比以前排序得更好，所以你知道它将是循环运行次数的 O(n) 倍。您在分析中尚未完成的是讨论在所有内容最终排序之前该循环可以运行多少次。

关于冒泡排序，您可以观察到在第一次遍历数组后，最大的元素肯定位于最后一个位置 - 您能解释一下原因吗？第二遍之后，第二大元素保证在倒数第二个位置——再一次，你能解释一下为什么吗？基于这个模式，你能争论为什么外层循环运行的次数最多为 O(n) 吗？