如何在时间复杂度方面改进算法？

Question

我正在尝试测量算法的时间复杂度：

public boolean rotateAndCompare(int[] fst, int[] snd) {
    int len = fst.length;
    for (int k = 0; k < len; k++) {
        for (int j = 0; j < len; j++) {
            if (fst[(k + j) % len] != snd[j]) {
                break;
            }
            if (j == len - 1) {
                return true;
            }
        }
    }
    return false;
}

我假设它具有 O(n*n) 复杂性，因为我们遍历一个数组，然后遍历另一个数组。我对吗？如果是这样，我该如何改进它？

Answer 1

O(n*n)通常表示为"order n-squared"，O(n^2)，你的算法就是。但是，由于您绝对不进行长度检查，因此它可能会完全崩溃，这比算法复杂性更严重。 'snd'（那代表什么？为什么这么简洁？）甚至可能没有 'len' 元素。此外，您可以通过将终止条件作为循环控制的一部分而不是检查两次来获得一些改进。

崩溃的风险远比算法的复杂性严重。一旦解决了这个问题，您就可以重构索引以使其更线性，但我怀疑这是不可能的。如果您的问题中存在对称性，您也许可以利用它们。

Answer 2

如果我理解正确，你的算法会决定 snd 的前 fst.length 个整数是否等于 fst，可能是旋转的。它假定 snd.length >= fst.length。如果这不是你的意思，请在问题中说明。

但是假设这就是您的真正意思，您可以使用像 KMP 这样的字符串匹配算法在 O(n) 中解决这个问题。换句话说，您需要看看是否可以找到 snd 作为 fst + fst 的子数组，这是一个经典问题。

这是 Java 中的示例实现：

import java.util.Arrays;

public class Main {
    public static class KMP {
        private final int F[];
        private final int[] needle;

        public KMP(int[] needle) {
            this.needle = needle;
            this.F = new int[needle.length + 1];

            F[0] = 0;
            F[1] = 0;
            int i = 1, j = 0;
            while (i < needle.length) {
                if (needle[i] == needle[j])
                    F[++i] = ++j;
                else if (j == 0)
                    F[++i] = 0;
                else
                    j = F[j];
            }
        }

        public int find(int[] haystack) {
            int i = 0, j = 0;
            int n = haystack.length, m = needle.length;

            while (i - j <= n - m) {
                while (j < m) {
                    if (needle[j] == haystack[i]) {
                        i++;
                        j++;
                    } else break;
                }
                if (j == m) return i;
                else if (j == 0) i++;
                j = F[j];
            }
            return -1;
        }
    }

    public static boolean rotateAndCompare(int[] fst, int[] snd) {
        int[] fst2 = new int[fst.length * 2];
        System.arraycopy(fst, 0, fst2, 0, fst.length);
        System.arraycopy(fst, 0, fst2, fst.length, fst.length);

        int[] snd2 = Arrays.copyOf(snd, fst.length);
        return new KMP(snd2).find(fst2) >= 0;
    }

    public static void main(String[] args) {
        System.out.println(rotateAndCompare(new int[]{1, 2, 3}, new int[]{3, 1, 2, 4}));
        System.out.println(rotateAndCompare(new int[]{1, 2, 2}, new int[]{3, 1, 2, 4}));
    }
}

如何在时间复杂度方面改进算法？

How to improve algorithm with respect of time complexity?

java

algorithm

big-o

time-complexity