对三次变换数组进行排序

Question

问题是在执行三次函数后返回一个排序的数组。具体来说，给定一个排序数组nums(即，x0, x1, x2，…)在执行f(x) = ax^3 + bx^2 + C*x + d后，返回另一个排序数组。

野蛮力法(时间复杂度O(nlogn))

1. 输入数值到f(x)，得到y = f(x0)， f(x1)， f(x2)，…f (xn)
2. 对y排序得到答案

有没有更好的想法和解决方案?非常感谢您的建议和意见。

Answer 1

算算三次函数导数的零点(解3*a*x^2 + 2*b*x+c=0)并求最大值和最小值。分析极值之间的行为(正导数证明函数在增加)

结果曲线单调在它们之间，所以你有一些(1到3取决于x范围)系列，你可以反转递减系列，然后合并线性时间序列

Answer 2

在(纯)Python中(因为这是问题的标记)，您可能无法击败计算图像然后对其进行排序的天真/直接方法。除了特殊的输入，它甚至只需要线性时间，这要归功于Timsort识别最多三个单调部分并将它们合并。

让我们对@MBo的示例x^3 - 60000x^2 + x + 1, x=-10000..50000进行基准测试，x步长为0.01，因此我们有600万个点:

Round 1   Round 2   Round 3
1156 ms   1157 ms   1168 ms  transform
201 ms    202 ms    203 ms  copy+sort
92 ms     94 ms     93 ms  copy

所以在这里，即使转换已经花费了排序的10倍时间(1160 ms vs 202-93=109 ms，我在排序之前复制了转换后的值，因为我反复测试)。

如果你试图自己识别和合并单调部分，那将用更像1160 ms的东西代替109 ms，即更慢。

代码(在线试用!):

from timeit import repeat
def transform(a, b, c, d, X):
return [((a*x + b)*x + c)*x + d
for x in X]
funcs = [
('transform', lambda: transform(a, b, c, d, X)),
('copy+sort', lambda: Y.copy().sort()),
('copy',      lambda: Y.copy()),
]
a, b, c, d = 1., -60000., 1., 1.
X = [i / 100 for i in range(-1_000_000, 5_000_001)]
Y = transform(a, b, c, d, X)
number = 1
tss = [[] for _ in funcs]
for _ in range(3):
print(' Round 1   Round 2   Round 3')
for (label, func), ts in zip(funcs, tss):
t = min(repeat(func, number=number)) / number
ts.append(t)
print(*('%5d ms ' % (t * 1e3) for t in ts), label)
print()