arrays - 计算反转以查看数组是否部分排序

Question

下面排序数组的定义来自 Robert Sedgewick 和 Kevin Wayne 合着的算法书。

An array is partially sorted if the number of inversions is <= cN

不应该限制 c 的高度吗？难道我不能在技术上使 c = 1000000000 而现在很多未排序的数组在不应该的时候会被算作部分排序吗？我知道设置高 c 并不明智，但不应该是某种范围吗？

这是一个最坏情况的例子。

D C B A

反转计数

1 (d, c)

2 (d, b)

3 (d, a)

4 (c, b)

5 (c, a)

6 (b, a)

对于大小为 4、6 项的数组。如果 c = 2 和 6 < 4*2

，那是完全线性的

我们什么时候达到 N^2 范围？

Answer 1

嗯，从技术上讲，c 是有上限的因为你只能有这么多的反转(即 N(N-1)/2 )。

该算法针对 N 进行了推广和 c不是 N 的函数，它是一个常数。您需要确定 c根据您的要求。即使它是 N^2 的顺序对于 N 的某些值, 它仍然是一个常数，不会与 N^2 相提并论以获得更高的值(value)。因此，没有办法限制 c一般而言。

每当你有想筹集资金的冲动时c给建议N^2订购特定值 N ，做吧。然后保留c修复并提高 N几个数量级。然后享受将常量称为常量的奢侈，无论它有多大。

更新

将最大反转输入为 N(N+1)/2而不是 N(N-1)/2 .现已修复。