Сортировка по математике

Question

Учитывая отсортированный массив, я считаю, что можно создать уравнение для определения индекса, в который будет вставлено любое заданное число.

Например, с учетом отсортированного массива [-1, 0, 1], есть таблица ввода / вывода для моей желаемой функции, например:

 x  | f(x)
----------
-2  | 0
-1.5| 0
-1  | 0, 1
-0.5| 1
 0  | 1, 2
 0.5| 2
 1  | 2, 3
 1.5| 3
 2  | 3

Я решил использовать x в качестве числа, которое я хочу вставить в массив, и функция будет выводить индексы, которые функция вставки могла бы использовать для вставки x в отсортированный массив.

Меня интересует то, что, учитывая это упрощение проблемы, я замечаю две вещи:

• Выходные данные функции должны быть целыми числами
• В некоторых случаях функция может возвращать 2 разных значения

И здесь я оставляю свои мысли тем, у кого больше опыта, чем у меня ...

Моя первая мысль - что результат напоминает мне о картировании Карно. Существует два значения, которые могут быть получены в случаях, но не имеет значения, какой результат выбран.

Моя вторая мысль связана с квантовыми вычислениями. Я недостаточно опытен, чтобы быть конкретным, но если два функциональных выхода могут быть сопоставлены с кубитом и обработаны квантово, какие возможности это дает в таком контексте? Может ли квантовый компьютер помочь получить эту формулу, которую я ищу?

Мой пример очень прост, но я просто хотел поделиться этим здесь на случай, если кому-то будет интересно.

Answer 1

Полином степени n может быть однозначно определен как n+1 баллов. Тем не менее, вам понадобится многочлен, который может соответствовать вашим n+1 точкам, оставаясь монотонным. Я не совсем уверен, как этого добиться, но я уверен, что библиотеки подбора кривых уже решили это за нас. Вероятно, это просто означает добавление еще нескольких степеней свободы к полиному и минимизацию некоторых ограничений.

Что касается вашей заметки о суперпозиции - я сомневаюсь, что она имеет много последствий для мира квантовых вычислений. На самом деле, я бы сказал, что F не должно отображаться более чем на одно значение, так как это нарушит определение функции. Если есть два индекса, на которые он может отображаться, то это потому, что значения равны, и, следовательно, порядок не имеет значения, поэтому вы должны просто выбрать один (вставить до или вставить после равного значения), как вы должны сделать в реализация в любом случае.