сложность алгоритма foo - PullRequest
Новая
       19

сложность алгоритма foo

1 голос
/ 04 февраля 2011

У меня есть проблема, которую я не могу решить .. какова сложность этого алгоритма foo? 

int foo(char A[], int n, int m){
  int i, a=0;
  if (n>=m)
    return 0;
  for(i=n;i<m;i++)
    a+=A[i]  
  return a + foo(A, n*2, m/2);
}

функция foo вызывается: 

foo(A,1,strlen(A));

итак ... я думаю, это log (n) * что-то для внутреннего цикла for ... что я не уверен, что это log (n) или что ..

Может ли это быть тэта log ^ 2 (n)?

Ответы [ 2 ]

3 голосов
/ 05 февраля 2011

Это отличное применение основной теоремы:

Перепишите в терминах n и X = m-n: 

int foo(char A[], int n, int X){
  int i, a=0;
  if (X < 0) return 0;
  for(i=0;i<X;i++)
    a+=A[i+n]  
  return a + foo(A, n*2, (X-3n)/2);
}

Итак, сложность 

T(X, n) = X + T((X - 3n)/2, n*2)

Отмечая, что штраф увеличивается с X и уменьшается с n, 

T(X, n) < X + T(X/2, n)

Итак, мы можем рассмотреть сложность 

U(X) = X + U(X/2)

и включите это в основную теорему, чтобы найти U (X) = O (X) -> сложность O (m-n)

1 голос
/ 05 февраля 2011

Я не уверен, есть ли «быстрый и грязный» способ, но вы можете использовать старую добрую математику. Никаких причудливых теорем, только простые уравнения.

На k-м уровне рекурсии (k начинается с нуля) цикл будет иметь ~ n/(2^k) - 2^k итераций. Следовательно, общее количество итераций цикла будет S = sum(n/2^i) - sum(2^i) для 0 <= i <= l, где l - глубина рекурсии.

l будет приблизительно log(2, n)/2 (докажите это).

Преобразовав каждую часть в формулу для S по отдельности, получим. 

S = (1 + 2 + .. + 2^l)*n/2^l - (2^(l + 1) - 1) ~= 2*n - 2^(l + 1) ~= 2*n - sqrt(n)

Поскольку каждое другое утверждение, кроме цикла, будет повторяться только l раз, и мы знаем, что l ~= log(2, n), это не повлияет на сложность.

Итак, в итоге получаем O(n).

...