Какова временная сложность всего алгоритма?

Я новичок в асимптотической записи, и вот алгоритм. Какова наихудшая ситуация жесткой связи для сложности времени и почему?

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))

Другие вопросы по тегам