алгоритм от отсортированного массива до отсортированного полиномиального массива

Question

Работая над проблемой ниже, основная идея: (1) если A> 0, слейте с двух концов, и в этом случае два конца будут иметь большие значения по сравнению с серединой массива, (2), если A < 0, сливаются также с двух концов, и в этом случае два конца имеют меньшие значения по сравнению с серединой массива.

Хотите узнать, какие умные идеи для улучшения производительности (например, сложность по времени или другая перспектива), улучшение пространственной сложности или любые ошибки в моем коде?

Проблема,

Учитывая отсортированный массив целых чисел X и 3 целых чисел A, B и C. возвращают соответствующий массив сортируется полином.

Другими словами, примените A x x + B * x + C для каждого элемента x в массиве и вернуть отсортированный массив.

Исходный код в 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 

Найти минимальное или максимальное (х значение -B/2A). Если экстремумы находятся внутри вашего диапазона данных, получите индекс с экстремальным значением и заполнить выходной массив от начала (если минимум) или от конца (если максимум) в режиме слияния - вы уже реализовали своего рода слияние.

В этом случае (предварительное распределение памяти, не вставка) сложность не является линейным O (N)

Answer 2

Расширения отличного ответа от MBO, вот возможная реализация:

import bisect 
import heapq 

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

def sort_polynomial(numbers, a, b, c): 
    if a == 0: 
     return map(f(a, b, c), numbers)    # No x^2 term? Just map! 
    apex = -b/(2 * a)       # Find min or max 
    middle_index = bisect.bisect_left(numbers, apex) # Where to cut list in half 
    numbers = map(f(a, b, c), numbers)    # Apply f 
    l1 = numbers[0:middle_index]      # Part before apex 
    l2 = numbers[middle_index:]      # Part after apex 
    if a < 0: 
     l2.reverse()         # Revert after apex 
    else: 
     l1.reverse()         # Revert before apex 
    return list(heapq.merge(l1, l2))     # Merge and return 

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