algorithm - 我可以使用 if 语句而不是三重嵌套 for 循环来使我的算法更快吗？

Question

for (i = 1 to n)
  for (j = 1 to n)
    for (k = j+1 to n)
      if (A(i, j) = A(i, k)) return false;
for (k = 1 to n)
  for (i = 1 to n)
    for (j = i+1 to n)
      if (A(i, k) = A(j, k)) return false;

返回真；这里的伪代码是一种验证 n x n 矩阵是否为拉丁方的算法，但我的作业需要设计一个运行时间为 O(n^2) 的更快算法。所以，我在想，如果我简单地删除那两个第三个内部循环并更改为 if 语句，例如，

for (i = 1 to n)
  for (j = 1 to n)
    if (k <= n)
      k = j + 1;
      if (A(i, j) = A(i, k)) return false;
for (k = 1 to n)
  for (i = 1 to n)
    if (j <= n)
      j = i + 1;
      if (A(i, k) = A(j, k)) return false;

我已经在这个问题上卡了 2 个小时了，仍然一无所获。这个想法实际上来 self 的一个 friend 。只是为了验证我是否可以这样做，在删除第三个内部循环并添加if语句后，这个算法的运行时间是否变得更快？任何回应都会有所帮助，谢谢。

Answer 1

您的第二个代码块将无法正确进行验证:

• k 从不接收初始值。
• if (A(i, j) = A(i, k)) 归结为 if (A(i, j) = A(i, j+1)) ，这不足以作为测试:当它们不相邻时，这将不会检测到重复项。

一种具有O(n²) 时间复杂度的方法是使用 hash sets .许多编程语言都提供这种数据结构，允许插入和成员资格测试操作以 O(1) 时间复杂度(摊销)执行。

使用集合，您可以在 O(n) 中验证一行(或列)是否具有 n 个不同的值。为确保 n 个不同的值总体，您还可以使用集合。

下面是伪代码:

if A is not square: 
    return false
allValues = set()
for (i = 1 to n)
    rowValues = set()
    colValues = set()
    for (j = 1 to n)
        rowValues.add( A(i, j) )
        colValues.add( A(j, i) )
        allValues.add( A(i, j) )
    if (colValues.size != n) return false
    if (rowValues.size != n) return false
if (allValues.size != n) return false
return true

如果矩阵 A 中的值应该在 1..n 范围内，那么您也可以使用数组而不是集合。然后伪代码是这样的:

if A is not square: 
    return false
for (i = 1 to n)
    rowValues = Array(size = n).fillWith(0)
    colValues = Array(size = n).fillWith(0)
    for (j = 1 to n)
        if (A(i, j) < 1 or A(i, j) > n) return false
        if (rowValues( A(i, j) ) != 0) return false
        rowValues( A(i, j) ) = 1
        if (rowValues( A(j, i) ) != 0) return false
        colValues( A(j, i) ) = 1
return true