анализ наихудшего случая - PullRequest
Новая
       54

анализ наихудшего случая

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

Я изучаю наихудший анализ алгоритма

Для x> = 2, а rand (x) - это функция, которая возвращает 1 значение от 1 до x-1 с одинаковой вероятностью $ \ frac {1} { x-1} $ И max (x, y) выводит большее значение, а min (x, y) выводит меньшее значение Мне нужно найти сложность наихудшего случая для каждого алгоритма 

Algorithm A
Input=n
x=n
WHILE x>=2
  y=rand(x)
  x=max(y,x-y)

ALGORITHM B
Input =n
x=n
While x>=2
  y=rand(x)
  X=min(y,x-y)

ALGORITHM C
  Input : value n (integer)
  void fn(x :int)
     if(x>=2)
       y=rand(x)
       Fn(y)
       Fn(x-y)
     Else 
     Return 
  fn(n)

Для алгоритма A, когда x = 10, предположим, что rand () возвращает 1, затем max (1, x-1), поэтому наихудшим случаем будет O (n)

Для алгоритма B, когда x = 10, предположим, что rand () возвращает 4 из 10 он вызовет min (4,10-4), снова вызовет x = 4 et c, но наихудшим случаем будет x / 2 или (x-1) / 2

для алгоритма C

Он рекурсивный (?), Например, если x = 10 и y = rand (x) = 4, когда он вызывает Fn (4) и Fn (10-4 = 6), он будет снова и снова, пока не будет меньше 2 Но как найти порядок наихудшего случая?

1 Ответ

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

Алгоритм A: худший случай случается, когда X уменьшается настолько медленно, насколько это возможно. Максимально возможное значение X после одной итерации тела l oop равно X - 1 (поскольку это максимальное значение, которое может вернуть rand, а поскольку Y положительно, то X - Y должно быть меньше X). Следовательно, в наихудшем случае, когда rand всегда выбирает X - 1, время выполнения функции асимптотически ограничено линейной функцией - O (n).

Алгоритм B: наихудший случай происходит, когда X уменьшается так же медленно насколько это возможно. Максимально возможное значение X после одной итерации тела l oop равно floor (X / 2). Причина этого заключается в следующем: предположим, что Y меньше, чем пол (X / 2). Тогда min выберет Y, а не X - Y. Предположим, что вместо этого Y больше пола (X / 2). Тогда min выберет X - Y, а не Y. Следовательно, наихудший случай достигается, когда Y = floor (X / 2). Если мы допустим N = 2 ^ M, то X уменьшится вдвое около M раз. Это означает, что время выполнения асимптотически логарифмически c - O (log n).

Алгоритм C: мы можем записать отношение повторения для времени выполнения следующим образом: 

T(0) = a
T(1) = b
T(n) = T(f(n)) + T(n-f(n)) + c

Нам нужно найти функцию f (n), которая делает повторение настолько плохим, насколько это возможно. Давайте начнем исследовать n = 2, 3,…, k,… и посмотрим, появятся ли какие-либо шаблоны, которые могут сообщить нам о правильном выборе первых нескольких значений f (n): 

T(2) has only one split: Y=1, X-Y=1; so T(2) = 2a + c
T(3) has two equivalent splits: Y=1, X-Y=2; so T(3) = 3a + 2c
T(4) has two different splits:
    Y=1, X-Y=3: 4a + 3c
    Y=2, X-Y=2: 4a + 3c
    these end up being the same
T(5) has two different splits:
    Y=1, X-Y=4: 5a + 4c
    Y=2, X-Y=3: 5a + 4c
    these end up being the same
T(6) has three different splits:
    Y=1, X-Y=5: 6a + 5c
    Y=2, X-Y=4: 6a + 5c
    Y=3, X-Y=3: 6a + 5c
    these end up being the same

Все они оказываются абсолютно одинаковыми; выбор среди них, кажется, не имеет значения вообще. Это может быть связано с тем, что дополнительная работа на каждом этапе является постоянной; если бы это зависело от n, тогда анализ вполне мог бы получиться иначе. Выражение для каждого из рассмотренных нами значений n имело вид + c (n-1). Это линейная функция, поэтому мы ожидаем, что время выполнения этого алгоритма будет асимптотически линейным: O (n).

...