Big O обозначения сложности для двоичных multiplcation

Question

Что такое обозначение Big O для следующих операций:

А = 1 * (1 0 1 0) + 0 * (0 1 0 1)

---

Спасибо OlivierLi. Итак, пожалуйста, пожалуйста, об этом: A = 1 * (0 1 1 0 1 0 1 0) + 0 * (1 0 0 0 0 1 0 1) + 1 * (1 1 0 0 1 1 0 0) + 0 * (1 0 1 0 1 0 1 0). Это также O (1). Как вы видите, это как один двоичный бит, умноженный на 8 двоичных битов четыре раза. Если это также O (1), пожалуйста и ласково, как я могу это доказать. Спасибо вам с наилучшими пожеланиями.

Answer 1

Это O (1).

Это не зависит от какого-либо ввода вообще и всегда является постоянным.

Answer 2

Проблема в том, принимаем ли мы количество бит как переменную или константу.

Постоянное количество бит: сложность O (1), поскольку сложность одинакова для всех возможных номеров ввода.

Переменная количество бит: для каждого бита первого номера вы добавляете сдвинутое второе число. Учитывая, что сложение с произвольными длинными числами может иметь сложность O (N), конечная сложность O (N^2), где N - количество бит.