Какова временная сложность всего алгоритма?
Я новичок в асимптотической записи, и вот алгоритм. Какова наихудшая ситуация жесткой связи для сложности времени и почему?
F(A,B) { //A and B are positive
while A>0
print(A mod B)
A=A div B
}
2 ответа
Это не очень хороший вопрос. Во-первых, если B равен единице, алгоритм никогда не завершится. Предположительно B должно быть 2 или больше. Итак, у нас есть O(log A) шагов. Но теперь вопрос заключается в том, является ли само подразделение "операцией" или нет. Если A и B не ограничены, то по своей сути он также должен быть логарифмическим. Но обычно код будет работать на процессоре, который реализует все деления в 32 или 64 битах, и он не может делить число вне диапазона. Поэтому обычно мы говорим, что подразделения - это "операции".
Если мы говорим, что деление логарифмическое, а B мало, то мы O(log A)^2.
Временная сложность этого:
F(A,B) { //A and B are positive
while A>0
A=A/B
}
равно числу выполнений цикла, давайте назовем это l
и равно тому, сколько раз B должен разделить A, чтобы сделать "A > 0" ложным.
Из этого вопроса мы знаем, что:
Алгоритм D в 4.3.1 книги Кнута "Искусство компьютерного программирования" (том 2) выполняет любое длинное деление в O(m) шагах, где
m
это число цифр A, поэтому у нас есть верхняя граница.
Таким образом, Сложность Времени равна: *O(l * m)*
Теперь это:
print(A mod B)
Предполагая, что IO является постоянным (это, конечно, что-то не так в реальном мире), вам нужна сложность самого модуля, который из этого, мы знаем, это:
O (журнал A журнал B)
и побежит l
раз.
В результате мы имеем:
O (l * (m + log A log B))