Вычислительная сложность нахождения области по дискретной кривой - PullRequest
Новая
       12

Вычислительная сложность нахождения области по дискретной кривой

0 голосов
/ 04 ноября 2018

Я прошу прощения, если мои вопросы чрезвычайно ошибочны или плохо определены. Математика не мой самый сильный предмет. Для контекста я пытаюсь выяснить вычислительную сложность вычисления площади под дискретной кривой. В конкретном случае использования, который меня интересует, ось Y - это длина очереди, а ось X - время. Кривая всегда будет иметь следующие границы: она начинается с нуля, состоит из нескольких выборок с временными метками, которые больше нуля, и в конечном итоге сжимается до нуля. Мое первоначальное исследование дало два возможных математических подхода к этой проблеме. Первая - это сумма Реймана по области [a, b], где a изначально равен нулю, а b в конце концов становится равным нулю (не уверен, что мое понимание там полностью верно). Я думаю, что математическое представление этой формулы найдено здесь:

https://en.wikipedia.org/wiki/Riemann_sum#Connection_with_integration.

Второе - это дискретная свертка. Однако я не могу определить разницу между дискретной сверткой и суммой Реймана в области [a, b] и ее применимости в области [a, b], где a изначально равно нулю, а b в конце концов становится равным нулю.

Мои вопросы:

  • Есть ли разница между этими двумя?
  • Какой подход наиболее применим / эффективен для того, что я пытаюсь выяснить?
  • Уместно ли даже задавать вопрос о сложности вычислений любого математического подхода? Если да, то каковы сложности каждого в этом конкретном приложении?

Edit: Для дополнительного контекста будет существовать функция, вычисляющая среднюю длину очереди путем взятия суммы площади под двумя отдельными кривыми и деления ее на общий временной интервал, охватывающий эти две кривые. Конкретное применение можно увидеть на странице 168 этого документа: https://www.cse.wustl.edu/~jain/cv/raj_jain_paper4_decbit.pdf

Ответы [ 2 ]

0 голосов
/ 04 ноября 2018

Итак, это для фильтра обратной связи маршрутизатора в ссылочной статье ...

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

Работает, накапливая queue_length * time за каждый цикл.

  • В начале каждого «цикла» записывают текущую длину очереди и текущее время часов и устанавливают сумму текущего цикла равной 0. (В документе определяется цикл так, чтобы длина очереди равнялась 0 в начале, но это не важно)

  • каждый раз, когда длина очереди изменяется, получить новое текущее время часов и добавить (new_clock_time - previous_clock_time) * previous_queue_length к общему количеству. Также сделайте это в конце цикла. Затем , записать новую новую текущую длину очереди и текущее время часов.

  • Когда вам нужно вычислить текущую «среднюю длину очереди», это просто (previous_cycle_total + current_cycle_total + (current_clock_time - previous_clock_time) * previous_queue_length) / total_time_since_previous_cycle_start
0 голосов
/ 04 ноября 2018

Есть ли разница между ними?

A дискретная свертка требует двух функций. Если первый соответствует дискретной кривой, что является вторым?

Какой подход наиболее применим / эффективен для того, что я пытаюсь выяснить?

A сумма Римана является приближением интеграла . Обычно он используется для аппроксимации площади под непрерывной кривой. Конечно, вы можете использовать его на дискретной кривой, но это уже не приближение, и я не уверен, что вы можете назвать это суммой Римана.

Уместно ли даже задавать вопрос о сложности вычислений любого математического подхода? Если да, то каковы сложности каждого в этом конкретном приложении?

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

То, что вы, вероятно, хотите, выглядит как сумма Римана с трапециевидным правилом . Выберите первые две выборки, рассчитайте их среднее и умножьте на расстояние между двумя выборками. Повторите эти действия для каждой соседней пары и суммируйте их все.
...