Как рассчитать обозначение Big O следующего выражения? - PullRequest
Новая
       5

Как рассчитать обозначение Big O следующего выражения?

0 голосов
/ 14 января 2020

Я хочу найти обозначение Big O для следующего выражения.

enter image description here
Может ли оно быть представлено как enter image description here [где 1 <= l <= альфа, бета - это вектор целых чисел] <br>
Поправьте меня, если я ошибаюсь ....

1 Ответ

1 голос
/ 14 января 2020

Алгоритм вычисления этой суммы будет: 

BigInteger sum = BigInteger.ZERO;
for (int i = 1; i <= alpha; i++) {
     sum = sum.add(BigInteger.ONE.shiftLeft(beta[i]));
}

Теперь сложность N-битного сдвига или N-битного сложения с использованием BigInteger равна O(N).

* 1007. * Таким образом, общая сложность вычисления выше будет ограничена alpha * min(beta[i]) и alpha * max(beta[i]).

Кроме того, фактическая сложность также будет зависеть от порядка значений beta[i].

Если значения alpha и beta достаточно малы, чтобы Вы можете использовать примитивное целочисленное арифметическое c, тогда сложность равна O(alpha), поскольку как добавление, так и сдвиг являются O(1) операциями.

С другой стороны, если вам нужен класс сложности для эта функция, это будет что-то вроде O(alpha * 2 ^ (max(beta[i]))). Обратите внимание, что это на самом деле функция скаляра и вектора, и я не уверен, что это математически обоснованная вещь. (Что значит для вектора стремиться к бесконечности?)

...