Вычислительная сложность (обозначение Big-O) геометрического взвешенного центроида среди точек доступа - PullRequest
Новая
       15

Вычислительная сложность (обозначение Big-O) геометрического взвешенного центроида среди точек доступа

0 голосов
/ 18 мая 2018

Мне нужно вычислить вычислительную сложность следующих уравнений, используя обозначения Big-O:

enter image description here

Здесь m - общее числоточек доступа (возможно, число итераций с точки зрения сложности, i - отдельная точка доступа).Я узнал о форме записи Big-O в этом блоге.Более того, я нашел похожий вопрос на этой ссылке .В приведенном выше уравнении d - это расстояние, вычисленное с помощью 4 операций (умножение, вычитание, деление и мощность).Как видно из приведенного выше уравнения, w вычисляется с двумя операциями (мощность и деление).xw и yw вычисляются с двумя операциями каждая (умножение и деление).Следовательно, я вычислил обозначение Big-O вышеупомянутого алгоритма как: 

4*[m]+2*[m]+2*[m]+2*[m]

Это правильно?Может ли оно быть приблизительно O(m)?Кроме того, вышеупомянутый алгоритм (уравнения) объединяется со следующим алгоритмом, вычислительная сложность которого составляет O(N), N - количество итераций.Здесь N>>m.Какова будет конечная вычислительная сложность с точки зрения обозначения Big-O?

Спасибо.

ОБНОВЛЕНИЕ:

Индекс w с x и y - это просто обозначение.Это не итерация.Итерация составляет всего m.Например.i = 1,2,3,4,5,......,m. Два алгоритма работают по конвейеру.Например, сначала работает алгоритм с m итерациями, и выходные данные этого алгоритма передаются (как входные данные) в следующий алгоритм с N итерациями.Итак, когда m итераций (алгоритм 1) завершены, за этим следует N итераций (алгоритм 2).Моя проблема похожа на два цикла, которые не являются вложенными и имеют разные итерации, где N>>m.

for(int i=0; i<m; i++){
   System.out.println(i);
}

for(int j=0; j<N; j++){
   System.out.println(j);
}

Какова будет конечная вычислительная сложность?

1 Ответ

0 голосов
/ 18 мая 2018

Да, ваша сумма от i=1 до i=m занимает O(m) время.Все остальные операции являются постоянными, у вас нет какой-либо суммы на сумму или что-то вроде этого.

По поводу вашего значения N, вы не предоставили достаточно информации.Мы должны знать, как вычисляется N или как он связан с m.

Также следует учитывать следующее ограничение - можете ли вы предоставить какое-то максимальное (даже невероятно) максимальное значение, котороеникогда не может быть достигнуто числами или уравнениями?Обычно операции с числами считаются константами, потому что они выполняются на 32- или 64-битных числах, которые всегда занимают постоянное время.

Однако, если у вас есть некоторые уравнения с невероятно длинными числами (например, сотни символов или более),Размер чисел нужно учитывать в сложности.(Вы, вероятно, можете себе представить, что умножение двух чисел длиной в миллионы символов занимает больше, чем проделывание того же с 2x2)

...