这是关于一件课程，所以宁愿你没有完全回答这个问题，而是要给小费，以提高我目前的算法的运行时间复杂度的问题。

This is a question regarding a piece of coursework so would rather you didn't fully answer the question but rather give tips to improve the run time complexity of my current algorithm.

我已经给出了以下信息：

I have been given the following information:

一个函数g（n）由G（N）= F给定（N，N）其中f可通过递归

A function g(n) is given by g(n) = f(n,n) where f may be defined recursively by

我已经实现这个递归算法具有以下code：

I have implemented this algorithm recursively with the following code:

public static double f(int i, int j) 
{

    if (i == 0 && j == 0) {
        return 0;
    }
    if (i ==0 || j == 0) {
        return 1;
    }

    return ((f(i-1, j)) + (f(i-1, j-1)) + (f(i, j-1)))/3;
}

这个算法给我找的结果，但它是非常低效的，我现在的任务是提高了运行时的复杂性。

This algorithm gives the results I am looking for, but it is extremely inefficient and I am now tasked to improve the run time complexity.

我写的算法，创建一个n * n矩阵，它然后计算每个元素到[N] [N]的元素在其中，然后返回[N] [N]元素，例如f（1， 1）将返回0.6复发。的[n]的[n]的元素为0.6的重复，因为它是（1 + 0 + 1）/ 3的结果。

I wrote an algorithm to create an n*n matrix and it then computes every element up to the [n][n] element in which it then returns the [n][n] element, for example f(1,1) would return 0.6 recurring. The [n][n] element is 0.6 recurring because it is the result of (1+0+1)/3.

我还创建为F（0,0）的结果preadsheet到f（7,7），它可以看到下面：

I have also created a spreadsheet of the result from f(0,0) to f(7,7) which can be seen below:

现在虽然这是比我的递归算法要快很多，这有可能会造成* n矩阵的一个巨大的开销。

Now although this is much faster than my recursive algorithm, it has a huge overhead of creating a n*n matrix.

任何建议，我怎么能改善这个算法将大大AP preciated！

Any suggestions to how I can improve this algorithm will be greatly appreciated!

我现在可以看到，是有可能使算法为O（n）的复杂性，但有可能制定出结果，而无需创建一个[N] [N]二维数组？

I can now see that is it possible to make the algorithm O(n) complexity, but is it possible to work out the result without creating a [n][n] 2D array?

我已经创建了一个为O（n）时间及O（n）的空间，将发布解决方案，我已经递交了我的课程后，停止任何抄袭Java中的一个解决方案。

I have created a solution in Java that runs in O(n) time and O(n) space and will post the solution after I have handed in my coursework to stop any plagiarism.

推荐答案

这是另外一个问题，那些地方是更好地研究它，潜水和写作code之前。

This is another one of those questions where it's better to examine it, before diving in and writing code.

我说你应该做的第一件事是看数字网格，并没有重新present他们为小数，但分数代替。

The first thing i'd say you should do is look at a grid of the numbers, and to not represent them as decimals, but fractions instead.

这应该是显而易见的第一件事是，总数你是刚与原点的距离的量度，

The first thing that should be obvious is that the total number of you have is just a measure of the distance from the origin, .

如果你看一下在这样一个网格，你可以得到所有分母的：

If you look at a grid in this way, you can get all of the denominators:

请注意，第一行和列是不是所有的 1 的S - 他们已经选择遵循的模式，和一般公式适用于所有的其它的广场。

Note that the first row and column are not all 1s - they've been chosen to follow the pattern, and the general formula which works for all of the other squares.

而分子是一点点麻烦，但还是可行的。与大多数这类问题，得到的答复是相关的组合，阶乘，然后一些更复杂的东西。典型的项目包括在这里 Catalan数，的斯特林的数字，杨辉三角，你将几乎总是看到超几何函数的使用。

The numerators are a little bit more tricky, but still doable. As with most problems like this, the answer is related to combinations, factorials, and then some more complicated things. Typical entries here include Catalan numbers, Stirling's numbers, Pascal's triangle, and you will nearly always see Hypergeometric functions used.

除非你做的很多的数学，它不可能你熟悉所有这些，并有大量的文献的地狱。所以，我有一个简单的方法来找出你需要的关系，它几乎总是工作。它是这样的：

Unless you do a lot of maths, it's unlikely you're familiar with all of these, and there is a hell of a lot of literature. So I have an easier way to find out the relations you need, which nearly always works. It goes like this:

希望，结果从整数序列的在线百科全书弹出。

3.B。如果不存在的话，看在你的顺序，或一些其他的序列关系到你的数据有些差异。

3.b. If one doesn't, then look at some differences in your sequence, or some other sequence related to your data.

使用您找到实现该序列的信息。

Use the information you find to implement said sequence.

所以，按照这一逻辑，这里有而分子：

So, following this logic, here are the numerators:

现在，不幸的是，谷歌上搜索那些取得什么。不过，也有一些事情你可以看到他们，主要在于第一行/列的只是3权力，而第二行/列比三大强国之一更少。这种境界是完全一样的帕斯卡三角，以及大量相关的序列。

Now, unfortunately, googling those yielded nothing. However, there are a few things you can notice about them, the main being that the first row/column are just powers of 3, and that the second row/column are one less than powers of three. This kind boundary is exactly the same as Pascal's triangle, and a lot of related sequences.

下面是的分子和分母之间的差异矩阵：

Here is the matrix of differences between the numerators and denominators:

在哪里，我们已经决定，F（0,0）元素应该只是遵循相同的模式。这些数字已经看起来要简单得多。还注意到虽然 - 相当有趣的是，这些数字跟随相同的规则的初始数字 - 除了所述第一数量是一（并且它们由一个列和一个行偏移）。 T（I，J）= T（I-1，J）+ T（I，J-1）+ 3 * T（I-1，J-1）

Where we've decided that the f(0,0) element shall just follow the same pattern. These numbers already look much simpler. Also note though - rather interestingly, that these numbers follow the same rules as the initial numbers - except the that the first number is one (and they are offset by a column and a row). 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

这看起来更像你看到了很多在组合序列。

This looks more like the sequences you see a lot in combinatorics.

如果你从这个矩阵谷歌的数字，你得到一个打击。

，然后如果你切断链接到原始数据，你会得到序列 A081578 ，它被描述为一个Pascal-（1,3,1）阵，这完全是有道理 - 如果你旋转矩阵，使 0,0 元素是在顶部，和元素形成一个三角形，然后你把 1 * 左元素， 3 * 上述元素，而 1 * 右元素。

And then if you cut off the link to the raw data, you get sequence A081578, which is described as a "Pascal-(1,3,1) array", which exactly makes sense - if you rotate the matrix, so that the 0,0 element is at the top, and the elements form a triangle, then you take 1* the left element, 3* the above element, and 1* the right element.

现在的问题正在执行用于生成数字的公式。

The question now is implementing the formulae used to generate the numbers.

不幸的是，这往往是说易行难。例如，该公式给出在网页：

Unfortunately, this is often easier said than done. For example, the formula given on the page:

T（N，K）=总和{J = 0到n，C（K，JK）* C（N + KJ，K）* 3 ^（JK）}

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

is wrong, and it takes a fair bit of reading the paper (linked on the page) to work out the correct formula. The sections you want are proposition 26, corollary 28. The sequence is mentioned in Table 2 after proposition 13. Note that r=4

正确的公式给出的命题26，但也有一个错字有：/。该 K = 0 的总和应为 J = 0 ：

The correct formula is given in proposition 26, but there is also a typo there :/. The k=0 in the sum should be a j=0:

其中， T 是包含系数的三角矩阵。

Where T is the triangular matrix containing the coefficients.

在OEIS页面确实给一对夫妇的实现来计算的数字，但他们都不是在Java中，和他们都不可以轻松转录到Java：

The OEIS page does give a couple of implementations to calculate the numbers, but neither of them are in java, and neither of them can be easily transcribed to java:

有一个数学的例子：

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

其中，一如既往，是可笑简洁。而且还有一个Haskell的版本，这是同样简洁：

which, as always, is ridiculously succinct. And there is also a Haskell version, which is equally terse:

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实现：

I know you're doing this in java, but i could not be bothered to transcribe my answer to java (sorry). Here's a python implementation:

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

因此​​，对于一个封闭的形式：

So, for a closed form:

凡只是二项式系数。

Where the are just binomial coefficients.

下面的结果：

最后一个另外，如果您正在寻找这样做的大量涌现，那么你将需要计算二项式系数不同的方式，因为你会溢出的整数。你的答案是LAL浮点虽然，因为你是在大的明显兴趣 F（N）= T（N，N）那么我想你可以使用斯特灵公式或什么的。

One final addition, if you are looking to do this for large numbers, then you're going to need to compute the binomial coefficients a different way, as you'll overflow the integers. Your answers are lal floating point though, and since you're apparently interested in large f(n) = T(n,n) then I guess you could use Stirling's approximation or something.