有效确定矩阵中[n] [n]个元素的算法

Question

这是一个关于课程作业的问题,所以宁愿你没有完全回答这个问题,而是提出改进我当前算法的运行时复杂性的技巧.

我收到了以下信息:

函数g(n)由g(n)= f(n,n)给出,其中f可以递归地定义

我用以下代码递归地实现了这个算法:

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;
}

这个算法给出了我正在寻找的结果,但效率极低,我现在的任务是提高运行时间的复杂性.

我写了一个算法来创建一个n*n矩阵然后计算每个元素直到[n] [n]元素,然后它返回[n] [n]元素,例如f(1,1)会返回0.6重复出现.[n] [n]元素重复为0.6,因为它是(1 + 0 + 1)/ 3的结果.

我还创建了一个结果从f(0,0)到f(7,7)的电子表格,如下所示:

现在虽然这比我的递归算法快得多,但它创建一个*n矩阵的开销很大.

任何有关如何改进此算法的建议将不胜感激!

我现在可以看到有可能使算法O(n)复杂,但是有可能在不创建[n] [n] 2D数组的情况下计算出结果吗？

我已经在Java中创建了一个在O(n)时间和O(n)空间中运行的解决方案,并且在我递交课程以阻止任何抄袭之后将发布解决方案.

Answer 1

这是另一个问题,在潜入和编写代码之前,最好先检查它.

我要说你应该做的第一件事就是看一下数字的网格,而不是将它们表示为小数,而是表示分数.

首先应该明显的是总数 你只是衡量距起源的距离, .

如果以这种方式查看网格,您可以获得所有分母:

请注意,第一行和第二列不是全部1- 它们被选择为遵循模式,并且通用公式适用于所有其他方块.

分子有点棘手,但仍然可行.与大多数这样的问题一样,答案与组合,阶乘,然后是一些更复杂的事情有关.这里的典型条目包括加泰罗尼亚数字,斯特林数字,Pascal三角形,您几乎总会看到使用的超几何函数.

除非你做了很多数学,否则你不太可能熟悉所有这些,而且还有很多文献.所以我有一个更简单的方法来找出你需要的关系,这几乎总是有效的.它是这样的:

1. 写一个天真的,低效的算法来获得你想要的序列.
2. 将相当大量的数字复制到谷歌中.

3. 希望弹出整个在线百科全书序列的结果.

   3.B. 如果没有,那么请查看序列中的一些差异,或者与数据相关的其他序列.

4. 使用您找到的信息来实现所述序列.

所以,遵循这个逻辑,这里是分子:

不幸的是,现在谷歌搜索没有产生任何东西.但是,有一些事情你可以注意到它们,主要是第一行/列只是3的幂,第二行/列比3的幂少一个.这种边界与Pascal的三角形和许多相关的序列完全相同.

这是分子和分母之间的差异矩阵:

我们已经确定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,它被描述为"Pascal-(1,3,1)数组",这完全有意义 - 如果你旋转矩阵,那么0,0元素位于顶部,元素形成一个三角形,然后您获取1*左元素,3*上元素和1*右元素.

现在的问题是实现用于生成数字的公式.

不幸的是,这说起来容易做起来难.例如,页面上给出的公式:

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

这是错误的,需要花一点时间阅读论文(链接在页面上)来计算出正确的公式.你想要的部分是命题26,推论28.在命题13之后,表2中提到了序列.注意r=4

在命题26中给出了正确的公式,但在那里也有一个错字:/.将k=0在总和应该是j=0:

T包含系数的三角矩阵在哪里.

OEIS页面确实提供了几个实现来计算数字,但它们都不在java中,并且它们都不能轻易转录为java:

有一个mathematica示例:

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)我猜你可以使用斯特林的近似值.

Answer 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];