java - 使用快速排序对数组进行分区的运行时分析

Question

我正在写一篇关于学校快速排序的研究论文，因此我必须对我的算法的最佳和最坏情况进行精确的运行时分析，但我正在努力处理我的 while 语句部分。我明白为什么它的 log(n) 因为你有太多的递归调用你有 n/2^k = 1 并且这个等式给你 n = 2^k, k = log2(n) 等等......好吧我确实理解这部分的递归调用并不重要，但重要的是我的以下代码:

   }

        }

我必须根据我的元素 n 为每个语句指定“成本”。所以我为每个 if 语句添加了一个 +1，因为它们是简单的语句，现在我不知道如何获得 while 循环的成本。外循环运行直到指针 i 和 j 交叉，因此外循环至少执行 n/2+1(+1 表示退出条件)——但我无法找出内部两个 while 循环运行的频率。我以为它们也会运行 n/2 次，但这行不通，因为我们的老师告诉我们，每当我们有嵌套语句时，我们必须乘以成本，这将导致 (n/2+1)*((n/2 )+1)+((n/2)+1)) 这显然是 n^2 而不是 O(n) ...是的，我必须为每个中止条件和 if 语句添加一个 +1，尽管它们并不重要......我希望你能帮助我，告诉我我的错误是什么，我得到了一个 O(n^2) 运行时间，尽管它必须是 O(n)

旁注:我认为对于 while 循环来说，它是最好还是最坏的情况并不重要，所以不要介意

提前致谢冠军银牌

Answer 1

最坏情况运行时间为 O(n) 的原因是，如果仔细查看代码，您会发现最多访问每个数组索引一次:观察到索引 i 只会增加大小，而索引 j 只会减少，因此您最多对每个索引进行一次。

例如，如果您有一个大小为 10 的数组 a[]，则初始索引 i 将为 0，而 j将是 9。x 将(随机地)介于两者之间，比方说 x=4。然后，外部 while 循环进入，第一个内部 while 循环增加索引 i 直到 a[i] >= a[x]。第二个内部 while 循环对索引 j 执行相同的操作，但方向相反。

但是两个内部循环的总迭代次数之和最多为 10。此时下一个外部 while 循环检查将返回 false，并且不会发生第二次迭代。