Как рассчитать стоимость алгоритма?

Question

Я должен рассчитать стоимость этого алгоритма.

Я думал об экспоненциальной стоимости. Я попробовал рекуррентное соотношение. 4*T(n/4) + c*n и в конце концов это ((4^n) - 1)/3,

Это верно? Существуют ли другие методы для его расчета?

int m(int a[][]) {
    return m1(a, 0, a.length-1, 0, a[0].length-1);
}

int m1(int a[][], int l1, int l2, int c1, int c2) {
  if(c1 > c2 || l1 > l2) return 0;
  if(c1 == c2 && l1 == l2) return a[l1][c1];
  int c = (c1+c2)/2,
      l = (l1+l2)/2;

  return m1(a, l1, l, c1, c) + 
         m1(a, l1, l, c+1, c2) + 
         m1(a, l+1, l2,c1, c) + 
         m1(a, l+1, l2, c+1, c2);
}

Answer 1

Рекуррентное соотношение принимает вид:

      T(n) = A * T(n / B) + O(f(n))

ГдеA * T(n / B)представляет рекурсивный вызов функции иO(f(n))представляет работу, проделанную во время каждого вызова функции.

Для этого случая можно четко разделить код на две составляющие:

1. Работа, проделанная во время вызова функции:

      if(c1 > c2 || l1 > l2) return 0;
if(c1 == c2 && l1 == l2) return a[l1][c1];
int c = (c1+c2)/2,
    l = (l1+l2)/2;

2. И рекурсивные вызовы функции:

        return m1(a, l1, l, c1, c) + 
         m1(a, l1, l, c+1, c2) + 
         m1(a, l+1, l2,c1, c) + 
         m1(a, l+1, l2, c+1, c2);

Братьn = |a|. Когда вы делаете рекурсивный вызов, каждый вызов работает с непересекающимся квадрантом входной матрицы для вызова. Вы делаете 4 таких рекурсивных вызова, поэтому ваше рекуррентное отношение начинается так:

      T(n) = 4 * T(n / 4) ...

Затем вы перенастраиваете свое внимание на то, сколько работы выполняется при каждом вызове функции. В этом случае работаO(1). Напомним, что мы оцениваем принадлежность функции к Big O на основе размера ее входных данных. В этом случае размер входных данных равен размеру матрицы , которую мы определили количественно как . Таким образом, вопрос, который вы должны задать себе, когда пытаетесь оценить, сколько работы выполняется при каждом вызове этой функции, звучит так: «Когда становится сколь угодно большим, как изменяется стоимость этой конкретной операции?»

Давайте ответим на этот вопрос для каждой из операций:

      if(c1 > c2 || l1 > l2) return 0;

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

Однако некоторые люди скажут, что стоимость этих арифметических операций на самом деле невелика.O(m)где количество битов в большем из двух чисел. (Использование, потому что занято.) Это технически верно, и я объясню «ответ» для обоих подходов ниже.

Предполагая, что основная арифметика O(1)...

В этом случае вся ваша индексная математика занимает время O (1), поэтому ваше рекуррентное отношение становится:

      T(n) = 4 * T(n / 4) + O(1)

Что срабатывает вовремя. Если вы разбиваете на измерения, это то, гдеhэто высота иwэто ширина. Достаточно легко, верно?

Предполагая, что основная арифметика равна O(m)...

Мы вышли на совершенно новый уровень сложности — поздравляем! Чтобы двигаться дальше, нам нужно подумать о том, что представляет собой. Как отмечалось выше, это количество битов в большем из двух чисел в любой операции сложения или вычитания. (Сложение и вычитание лежат в основе>,<,==,&&, и||операций.) Вопрос, который мы должны задать: когда число битов в этих индексах растет сколь угодно большим, как при этом будет меняться количество битов в этих индексах?

Очевидно, что если он действительно большой, вам понадобятся числа с большим количеством бит, чтобы выразить индексы для доступа к значениям в . И наоборот, если он остается очень маленьким, вам потребуется гораздо меньшее количество битов для представления ваших индексов. Но какова именно асимптотическая связь между иm?

Ну, предположим,1 by nматрица. Тогда вам понадобятся индексы, которые могут пройти весь путь доn - 1, правильный? Поскольку мы используем биты, это означает, что наши индексы должны иметь как минимум биты (есть классный способ вычислить точное количество необходимых битов, но здесь он не рассматривается).

Таким образом, мы можем быть немного пессимистичными (т.е. немного переоценивать) и сказать, что для любой матрицыaс величинойn, нам нужно, чтобы все индексы имелиO(log n)биты. Другими словами,m = O(log n). Это означает, что каждая базовая арифметическая операция (сложение, вычитание, побитовые операции) на самом деле будет стоитьO(m) = O(log n)время. Итак, теперь ваше рекуррентное отношение становится:

      T(n) = 4 * T(n / 4) + O(log n)

... который по-прежнему оценивается какO(n)время! (Также известен какO(hw)как было сказано ранее.)

Надеюсь это поможет! :)

Answer 2

Насколько я могу судить: На каждом этапе мы делим проблемное пространство на четыре части. Чтобы объединить результаты подзадач, мы складываем вместе четыре целых числа, и эта операция выполняется за постоянное время. O(1).

Предполагать n- высота матрицы в вопросе, а mширина матрицы aв вопросе

Мы можем визуализировать сложность как 4-нарное дерево с n x mлистовые узлы и высота log4(nm). . Общее количество узлов в дереве равно , поэтому сложность O(nm).

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