python - 从排序数组到排序多项式数组的算法

Question

处理下面的问题，主要思想是，(1)如果 A > 0，从两端合并，在这种情况下，两端的值比数组的中间大，( 2) 如果 A < 0，也从两端合并，在这种情况下，两端的值比数组的中间值小。

想知道在我的代码中是否有更好的性能改进(例如时间复杂度或其他角度)、空间复杂度改进或任何错误的想法？

问题,

给定一个已排序的整数数组 X 和 3 个整数 A、B 和 C。返回对应的已排序多项式数组。

换句话说，对数组中的每个元素 x 应用 Axx + B*x + C 并返回排序后的数组。

Python 2.7 中的源代码,

def f(v, a, b, c):
    return a*v*v + b*v + c

def sort_polynomial(numbers, a, b, c):
    result = []
    if a > 0:
        start = 0
        end = len(numbers) - 1
        while start <= end:
            if f(numbers[start], a, b, c) <= f(numbers[end], a, b, c):
                result.insert(0, (numbers[end], f(numbers[end], a, b, c)))
                end -= 1
            else:
                result.insert(0, (numbers[start], f(numbers[start], a, b, c)))
                start += 1
    elif a < 0:
        start = 0
        end = len(numbers) - 1
        while start <= end:
            if f(numbers[start], a, b, c) <= f(numbers[end], a, b, c):
                result.append((numbers[start], f(numbers[start], a, b, c)))
                start += 1
            else:
                result.append((numbers[end], f(numbers[end], a, b, c)))
                end -= 1
    else:
        raise Exception('invalid argument!')

    return result

if __name__ == "__main__":
    numbers = [-2, -1, 0, 1, 2]
    print sort_polynomial(numbers, 1, 2, 1)
    print sort_polynomial(numbers, -1, 2, 1)

Answer 1

你有功能

F(x) = A*x^2 + B * x + C

查找最小值或最大值(x 值 -B/2A)。如果极值在您的数据范围内，则获取具有极值的索引并以合并方式从开头(如果最小)或从结尾(如果最大)填充输出数组 - 您已经实现了一种合并。

在这种情况下(初步内存分配，没有插入)复杂度是线性的 O(N)