gpt4 book ai didi

algorithm - 修改后的 MergeSort 的复杂性

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:21:15 25 4
gpt4 key购买 nike

我想在使用合并排序对数组进行排序时计算倒置。为此,我在条件语句中添加了一个变量,以便在遇到反转时该变量会递增。伪代码:

mergesort(M, l, r) begin
if (l < r) then
int m <- (l + r - 1)/2; //for rounding down I use explicitly int
inv <- 0; //set number of inversions
mergesort(M, l, m)
mergesort(M, m+1, r)
i <- l;
j <- m + 1;
k <- l;
while(i <= m and j <= r) do
if (M[i] <= M[j]) then
M'[k] <- M[i];
i <- i + 1;
else
M'[k] <- M[j];
j <- j + 1;
inv <- inv + 1; //Counting inversions
k <- k + 1;
for (h = i, .. , m) do
M[k + (h - 1)] <- M[h];
for (h = l, .. , k -1) do
M[h] <- M'[h];
end.

但是我不确定复杂度是否保持不变:O(n log n)。

仅增加一个变量是否会导致更差的 WC 复杂度?据我所知,它仅取决于最大的加数(n 因子)。并且添加一个常数或最坏情况下 (n - 1) + (n - 2) = 2n - 3 增量会大大改变复杂性吗?如果是,您有什么建议?

最佳答案

如果你看这两行

    j <- j + 1;
inv <- inv + 1; //Counting inversions

它们都是T(1)算术运算,它们处于相同的深度,因此 T(1)+T(1) = T(1) . inv <- inv + 1; 的额外行无法改变复杂性,因为执行时间保持不变。

关于algorithm - 修改后的 MergeSort 的复杂性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33650687/

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