Временная сложность (обозначение Big-O) вычисления апостериорной вероятности - PullRequest
Новая
       16

Временная сложность (обозначение Big-O) вычисления апостериорной вероятности

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

Я получил базовое представление о нотации Big-O из Определение нотации Big-O .

В моей задаче двумерная поверхность делится на однородную M сетки.Каждой сетке ( m ) присваивается апостериорная вероятность на основе A признаков.

Апостериорная вероятность сетки m рассчитывается следующим образом:

enter image description here
, а предельная вероятность определяется как:

marginal likelihood

Здесь функции A не зависят друг от друга, а сигма и означают * 1033Символ * обозначает стандартное отклонение и среднее значение каждой функции a в каждой сетке.Мне нужно вычислить апостериорную вероятность всех M сеток.

Какова будет временная сложность вышеуказанной операции в терминах записи Big-O?

Я предполагаю, что O (M) или O (M + A),Я прав?Я ожидаю, что аутентичный ответ будет представлен на официальном форуме.

Кроме того, какова будет временная сложность, если M сеток разделены на T кластеров, где каждый кластер имеет Q сеток ( Q << <em>M ) (вычисление апостериорной вероятности только для Q сеток из M сеток)?

Большое спасибо.

1 Ответ

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

Дискретная сумма и произведение

enter image description here

можно понимать как циклы.Если вас устраивает приближение с плавающей запятой, большинство других операторов обычно O (1), условная вероятность выглядит как вызов функции.Просто введите константы и переменные в ваше уравнение, и вы получите ожидаемый Big-O, детали формулы не имеют значения.Также имейте в виду, что эти «циклы» часто можно упростить с помощью математических свойств.

Если результат неочевиден, пожалуйста, преобразуйте приведенную выше математическую формулу в реальный код программирования на языке программирования.Информатика Big-O - это никогда не формула, а фактический перевод ее на этапах программирования, в зависимости от реализации одна и та же формула может привести к очень различным сложностям выполнения.Так же, как добавление целых чисел путем фактического выполнения суммы O (n) или применения, например, формулы Гаусса O (1).

Кстати, почему вы делаете дискретную сумму для дискретного домена N?Разве это не должно быть М?

...