Определить время выполнения для нескольких вызовов функции - PullRequest
Новая
       12

Определить время выполнения для нескольких вызовов функции

0 голосов
/ 02 мая 2019

Предположим, у меня есть функция f (K), которая выполняется в амортизированном логарифмическом времени в K, но в линейном худшем случае. Что такое время работы: 

    for i in range(N): f(N) (Choose the smallest correct estimate)
  • A. Линейное в N
  • B. Амортизированный линейный в Н
  • C. Квадратичный в N
  • D. Невозможно сказать по приведенной информации

Скажем, f (N) просто печатает «Hello World», поэтому он не зависит от того, насколько велик параметр. Можно ли сказать, что общее время работы линейно амортизируется в N?

1 Ответ

1 голос
/ 02 мая 2019

Этот вид выглядит как тестовый вопрос, поэтому вместо того, чтобы просто сказать ответ, позвольте мне объяснить, что означает каждая из этих концепций алгоритмической сложности.

Давайте начнем с утверждения function f(n) runs in constant time.Я знаю, что это даже не упомянуто в вопросе, но это действительно основа для понимания всех других алгоритмических сложностей.Если какая-то функция выполняется в постоянное время, это означает, что ее время выполнения не зависит от ее входных параметров.Обратите внимание, что это может быть просто print Hello World или return n или сложным, например, поиск первых 1 000 000 000 простых чисел (что, очевидно, занимает некоторое время, но занимает одинаковое количество времени при каждом вызове).Тем не менее, этот последний пример является скорее злоупотреблением математической нотацией;обычно функции с постоянным временем бывают быстрыми.

Теперь, что это значит, если функция f(n) работает с амортизированным постоянным временем?Это означает, что если вы вызываете функцию один раз, нет гарантии, как быстро она завершится;но если вы называете это n раз, сумма потраченного времени будет O(n) (и, таким образом, каждый вызов в среднем занимал O(1)). Здесь - более длинное объяснение из другого ответа StackOverflow.Я не могу представить себе какие-либо чрезвычайно простые функции, которые выполняются в амортизированном постоянном времени (но не постоянном времени), но вот один нетривиальный пример: 

called = 0
next_heavy = 1
def f(n):
  called += 1
  if called == next_heavy:
    for i in range(n):
      print i
    next_heavy *= 2

При 512-м вызове эта функция будетнапечатать 512 номеров;однако, до этого было напечатано всего 511, поэтому общее количество отпечатков равно 2*n-1, что составляет O(n).(Почему 511? Потому что сумма степеней двух от 1 до 2^k равна 2^(k+1).)

Обратите внимание, что каждая функция с постоянным временем также является амортизированной функцией с постоянным временем, потому что она требует O(n) времени дляn звонки.Таким образом, не амортизированная сложность немного строже, чем амортизированная.

Теперь в вашем вопросе упоминается функция с амортизированным логарифмическим временем, что, как и выше, означает, что после n вызовов этой функции общее время выполнения составляет O(nlogn) (и среднее время выполнения на один звонок O(logn)).И затем, на вопрос, эта функция вызывается в цикле от 1 до N, и мы только что сказали, что по определению эти N вызовы вместе будут выполняться в O(NlogN).Это linearithmic .

Что касается второй части вашего вопроса, можете ли вы определить, каково общее время работы цикла, основываясь на наших предыдущих наблюдениях?

...