Алгоритм для эффективного определения элемента [n] [n] в матрице

Ответ 1

Это еще один из тех вопросов, где лучше изучить его, прежде чем погружаться и писать код.

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

Первое, что должно быть очевидно, это то, что общее количество , которое у вас есть, является только мерой расстояния от начала координат, .

Если вы посмотрите на сетку таким образом, вы можете получить все знаменатели:

Обратите внимание, что первая строка и столбец не все 1 - они выбраны для отслеживания шаблона и общей формулы, которая работает для всех других квадратов.

Числители немного сложнее, но все же выполнимы. Как и в большинстве подобных проблем, ответ связан с комбинациями, факториалами, а затем с некоторыми более сложными вещами. Типичные записи здесь включают Каталонские номера, номера Стирлинга, Треугольник Паскаля, и вы почти всегда увидите Гипергеометрические функции используется.

Если вы не делаете много математики, вряд ли вы знакомы со всеми этими, и есть много литературы. Поэтому у меня есть более простой способ узнать отношения, которые вам нужны, что почти всегда работает. Это происходит следующим образом:

• Напишите наивный, неэффективный алгоритм, чтобы получить нужную вам последовательность.
• Скопируйте достаточное количество чисел в Google.

• Надеемся, что появится результат Online Encyclopedia of Integer Sequences.

  3.b. Если вы этого не сделаете, посмотрите на некоторые различия в вашей последовательности или на другую последовательность, связанную с вашими данными.

• Используйте информацию, которую вы найдете для реализации указанной последовательности.

Итак, следуя этой логике, вот числители:

Теперь, к сожалению, googling ничего не давали. Тем не менее, есть несколько вещей, которые вы можете заметить о них, главным из которых является то, что первая строка/столбец равна просто 3, а вторая строка/столбец меньше трех. Граница этого типа точно такая же, как треугольник Паскаля, и множество связанных последовательностей.

Вот матрица различий между числителями и знаменателями:

Если мы решили, что элемент f (0,0) должен следовать одному и тому же шаблону. Эти цифры уже выглядят намного проще. Также обратите внимание, что - довольно интересно, что эти числа соответствуют тем же правилам, что и начальные числа, за исключением того, что первое число равно одному (и они смещены по столбцу и строке). T(i,j) = T(i-1,j) + T(i,j-1) + 3*T(i-1,j-1):

                     1 
                  1     1
               1     5     1
            1     9     9     1
         1     13    33    13    1
      1     17    73    73    17    1
   1     21    129   245   192   21    1
1     25    201   593   593   201   25    1

Это больше похоже на последовательности, которые вы видите много в комбинатонике.

Если вы указали номера Google из этой матрицы, вы получите хиты.

И затем, если вы отключите ссылку на необработанные данные, вы получите последовательность A081578, которая описана как "Паскаль - (1,3,1) array", что в точности имеет смысл - если вы вращаете матрицу, так что элемент 0,0 находится вверху, а элементы образуют треугольник, то вы берете 1* левый элемент, 3* указанный выше элемент и 1* правый элемент.

Теперь возникает вопрос о реализации формул, используемых для генерации чисел.

К сожалению, это часто легче сказать, чем сделать. Например, формула, приведенная на странице:

T (n, k) = sum {j = 0..n, C (k, j-k) * C (n + k-j, k) * 3 ^ (j-k)}

неверно, и для получения правильной формулы требуется справедливая часть чтения статьи (ссылка на странице). Секции, которые вы хотите, являются предложением 26, следствием 28. Последовательность упоминается в таблице 2 после предложения 13. Обратите внимание, что r=4

Правильная формула дана в предложении 26, но там также есть опечатка:/. Сумма k=0 в сумме должна быть j=0:

Где T - треугольная матрица, содержащая коэффициенты.

Страница OEIS предоставляет несколько реализаций для вычисления чисел, но ни одна из них не находится в java, и ни одна из них не может быть легко расшифрована для java:

Существует математический пример:

Table[ Hypergeometric2F1[-k, k-n, 1, 4], {n, 0, 10}, {k, 0, n}] // Flatten 

который, как всегда, смехотворно лаконичен. И есть также версия Haskell, которая одинаково красная:

a081578 n k = a081578_tabl !! n !! k
a081578_row n = a081578_tabl !! n
a081578_tabl = map fst $ iterate
   (\(us, vs) -> (vs, zipWith (+) (map (* 3) ([0] ++ us ++ [0])) $
                      zipWith (+) ([0] ++ vs) (vs ++ [0]))) ([1], [1, 1])

Я знаю, что вы делаете это в java, но я не мог потрудиться, чтобы расшифровать мой ответ на java (извините). Здесь реализована реализация python:

from __future__ import division
import math

#
# Helper functions
#

def cache(function):
  cachedResults = {}
  def wrapper(*args):
    if args in cachedResults:
      return cachedResults[args]
    else:
      result = function(*args)
      cachedResults[args] = result
      return result
  return wrapper


@cache
def fact(n):
 return math.factorial(n)

@cache
def binomial(n,k):
  if n < k: return 0
  return fact(n) / ( fact(k) * fact(n-k) )





def numerator(i,j):
  """
  Naive way to calculate numerator
  """
  if i == j == 0:
    return 0
  elif i == 0 or j == 0:
    return 3**(max(i,j)-1)
  else:
    return numerator(i-1,j) + numerator(i,j-1) + 3*numerator(i-1,j-1)

def denominator(i,j):
  return 3**(i+j-1)



def A081578(n,k):
  """
  http://oeis.org/A081578
  """
  total = 0
  for j in range(n-k+1):
    total += binomial(k, j) * binomial(n-k, j) * 4**(j)
  return int(total)

def diff(i,j):
  """
  Difference between the numerator, and the denominator. 
  Answer will then be 1-diff/denom.
  """
  if i == j == 0:
    return 1/3
  elif i==0 or j==0:
    return 0
  else:
    return A081578(j+i-2,i-1)

def answer(i,j):
  return 1 - diff(i,j) / denominator(i,j)




# And a little bit at the end to demonstrate it works.
N, M = 10,10

for i in range(N):
  row = "%10.5f"*M % tuple([numerator(i,j)/denominator(i,j) for j in range(M)])
  print row

print ""
for i in range(N):
  row = "%10.5f"*M % tuple([answer(i,j) for j in range(M)])
  print row

Итак, для замкнутой формы:

Где - только биномиальные коэффициенты.

Здесь результат:

Последнее дополнение, если вы хотите сделать это для больших чисел, тогда вам нужно будет вычислить биномиальные коэффициенты другим способом, так как вы переполните целые числа. Однако ваши ответы - это лал с плавающей точкой, и, поскольку вы, по-видимому, заинтересованы в больших f(n) = T(n,n), то, я думаю, вы могли бы использовать приближение Стирлинга или что-то в этом роде.

Ответ 2

Хорошо для начинающих здесь есть некоторые вещи, которые нужно иметь в виду:

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

if (x == 0 && y == 0) {
    matrix[x][y] = 0;
}

Вместо этого вы должны: matrix[0][0] = 0; перед тем, как ввести первый цикл и установить x в 1. Поскольку вы знаете, что x никогда не будет 0, вы можете удалить первую часть своего второго условия x == 0:

for(int x = 1; x <= i; x++)
        {
            for(int y = 0; y <= j; y++)
            {             
                if (y == 0) {
                    matrix[x][y] = 1;
                }
                else
                matrix[x][y] = (matrix[x-1][y] + matrix[x-1][y-1] + matrix[x][y-1])/3;
            }
        }

Нет смысла объявлять строку и столбец, поскольку вы используете ее только один раз. double[][] matrix = new double[i+1][j+1];

Ответ 3

Чтобы описать временную сложность, мы обычно используем большую нотацию O. Важно помнить, что он описывает только рост с учетом ввода. O (n) - линейная временная сложность, но она не говорит, как быстро (или медленно) время увеличивается, когда мы увеличиваем ввод. Например:

n=3 -> 30 seconds
n=4 -> 40 seconds
n=5 -> 50 seconds

Это O (n), мы можем ясно видеть, что каждое увеличение n увеличивает время на 10 секунд.

n=3 -> 60 seconds
n=4 -> 80 seconds
n=5 -> 100 seconds

Это также O (n), хотя для каждого n нам нужно в два раза больше времени, а рейз - 20 секунд для каждого увеличения n, временная сложность растет линейно.

Итак, если у вас есть сложность времени O (n * n), и вы получите половину количества выполняемых вами операций, вы получите O (0.5 * n * n), равную O (n * n) - то есть ваш временная сложность не изменится.

Это теория, на практике количество операций иногда имеет значение. Поскольку у вас есть сетка n на n, вам нужно заполнить n * n ячеек, поэтому наилучшей временной сложностью, которую вы можете достичь, является O (n * n), но вы можете сделать несколько оптимизаций:

• Клетки на краях сетки могут быть заполнены отдельными петлями. В настоящее время в большинстве случаев у вас есть два ненужных условия для я и j, равных 0.
• У вашей сетки есть линия симметрии, вы можете использовать ее, чтобы вычислить только ее половину, а затем скопировать результаты на другую половину. Для каждого я и j grid[i][j] = grid[j][i]

В заключение отметим, что четкость и читаемость кода гораздо важнее производительности - если вы можете читать и понимать код, вы можете его изменить, но если код настолько уродлив, что вы не можете его понять, вы не можете оптимизируйте его. Вот почему я бы сделал только первую оптимизацию (это также повышает удобочитаемость), но не сделает второй - это сделает код намного сложнее понять.

Как правило, не оптимизируйте код, если только производительность не вызывает проблем. Как сказал Уильям Вульф:

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

EDIT:

Я думаю, что возможно реализовать эту функцию с помощью O (1) сложности. Хотя это не дает никаких преимуществ, когда вам нужно заполнить всю сетку, с временной сложностью O (1) вы можете мгновенно получить любое значение без сетки вообще.

Несколько наблюдений:

• Знак
• равен 3 ^ (i + j - 1)
• если я = 2 или j = 2, числитель на единицу меньше знаменателя

ИЗМЕНИТЬ 2:

Числитель может быть выражен следующей функцией:

public static int n(int i, int j) {
    if (i == 1 || j == 1) {
        return 1;
    } else {
        return 3 * n(i - 1, j - 1) + n(i - 1, j) + n(i, j - 1);
    }
}

Очень похож на оригинальную задачу, но никакое деление и все числа не являются целыми числами.

Ответ 4

Этот алгоритм имеет минимальную сложность Ω(n), потому что вам просто нужно умножить значения в первом столбце и строке матрицы с некоторыми факторами, а затем добавить их. Факторы обусловлены разворачиванием рекурсии n раз.

Однако вам необходимо выполнить разматывание рекурсии. Это само по себе имеет сложность O(n^2). Но балансируя разматывание и оценку рекурсии, вы должны уметь уменьшить сложность до O(n^x), где 1 <= x <= 2. Это похоже на алгоритмы для матрично-матричного умножения, где наивный случай имеет сложность O(n^3), но алгоритм Штрассеенса - это, например, O(n^2.807).

Другим моментом является тот факт, что исходная формула использует коэффициент 1/3. Так как это неточно представимо числами с фиксированной точкой или т.п. 754 с плавающей запятой, ошибка увеличивается при последовательной оценке рекурсии. Поэтому раскручивание рекурсии может дать вам более высокую точность как хороший побочный эффект.

Например, когда вы разматываете рекурсию sqr(n) раз, у вас есть сложность O((sqr(n))^2+(n/sqr(n))^2). Первая часть предназначена для разматывания, а вторая - для оценки новой матрицы размера n/sqr(n). Эта новая сложность на самом деле может быть упрощена до O(n).

Ответ 5

Если вопрос о том, как вывести все значения функции для 0<=i<N, 0<=j<N, вот решение во времени O(N²) и пробел O(N). Поведение времени оптимальное.

Use a temporary array T of N numbers and set it to all ones, except for the first element.

Then row by row,

    use a temporary element TT and set it to 1,
    then column by column, assign simultaneously T[I-1], TT = TT, (TT + T[I-1] + T[I])/3.

Ответ 6

Спасибо за ответ (первый), у меня была эта идея:

Считаем, что любое положительное решение приходит только от 1 вдоль осей x и y. Каждый из рекурсивных вызовов f делит каждую компоненту решения на 3, что означает, что мы можем суммировать, комбинаторно, сколько способов каждый 1 показывает как компонент решения и рассматривает его как "расстояние" (измеренное как сколько звонков f от цели) как отрицательная мощность 3.

Код JavaScript:

function f(n){

  var result = 0;

  for (var d=n; d<2*n; d++){

    var temp = 0;

    for (var NE=0; NE<2*n-d; NE++){

      temp += choose(n,NE);
    }

    result += choose(d - 1,d - n) * temp / Math.pow(3,d);
  }

  return 2 * result;
 }

function choose(n,k){
  if (k == 0 || n == k){
    return 1;
  }
  var product = n;
  for (var i=2; i<=k; i++){
    product *= (n + 1 - i) / i
  }
  return product;
}

Вывод:

for (var i=1; i<8; i++){
  console.log("F(" + i + "," + i + ") = " + f(i));
}

F(1,1) = 0.6666666666666666
F(2,2) = 0.8148148148148148
F(3,3) = 0.8641975308641975
F(4,4) = 0.8879743941472337
F(5,5) = 0.9024030889600163
F(6,6) = 0.9123609205913732
F(7,7) = 0.9197747256986194