O(log n) 编程

Question

我正在准备比赛，但我的程序速度总是非常慢，因为我使用 O(n)。首先，我什至不知道如何使它成为 O(log n)，或者我从未听说过这种范式。我在哪里可以了解这方面的知识？

例如，

如果您有一个包含零和一的整数数组，例如 [ 0, 0, 0, 1, 0, 1 ]，现在您想将每个 0 替换为 1 仅当一个它的邻居 的值为 1，如果这必须发生 t 次，最有效的方法是什么？（程序必须执行 t 次）

编辑：这是我低效的解决方案：

import java.util.Scanner;

public class Main {

static Scanner input = new Scanner(System.in);

public static void main(String[] args) {

    int n;
    long t;

    n = input.nextInt();
    t = input.nextLong();
    input.nextLine();

    int[] units = new int[n + 2];
    String inputted = input.nextLine();
    input.close();
    for(int i = 1; i <= n; i++) {
        units[i] = Integer.parseInt((""+inputted.charAt(i - 1)));
    }

    int[] original;

    for(int j = 0; j <= t -1; j++) {
        units[0] = units[n];
        units[n + 1] = units[1];
        original = units.clone();

        for(int i = 1; i <= n; i++) {
            if(((original[i - 1] == 0) && (original[i + 1] == 1)) || ((original[i - 1] == 1) && (original[i + 1] == 0))) {
                units[i] = 1;
            } else {
                units[i] = 0;
            }
        }

    }

    for(int i = 1; i <= n; i++) {
        System.out.print(units[i]);
    }
}

}

Answer 1

BigO 符号是理解算法复杂性的一种简化。基本上，两种算法 O(n) 可以有非常不同的执行时间。为什么？让我们展开您的示例：

您有两个嵌套循环。外循环将运行 t 次。
内循环会运行n次
每次循环执行，都会花费常数k次。

所以，本质上你的算法是 O(k * t * n)。如果t与n处于同一数量级，那么可以认为复杂度为O(k * n^ 2).

有两种优化算法的方法：

减少常数时间k。例如，不要每次循环都克隆整个数组，因为它非常耗时（克隆需要做一个完整的数组循环才能克隆）。
这种情况下的第二个优化是使用动态规划（https://en.wikipedia.org/wiki/Dynamic_programming）可以在两个循环之间缓存信息并优化执行，可以降低k或甚至将复杂度从 O(n^2) 降低到 O(n * log n)。

Answer 2

这是一个初等元胞自动机。这样的动力系统具有您可以利用的特性。例如，在您的情况下，您可以将与任何初始值 1（光锥属性）的距离最多为 t 的每个单元格设置为值 1。然后你可以这样做：

在原始序列中得到一个1，假设它位于位置p。
从p-t到p+t的每个位置都设置为1。

然后你可以在下一步中利用你已经将位置 p-t 设置为 p+t...这可以让你计算最后一步 t 而无需计算中间步骤（加速的好因素是不是吗？）。

你也可以像HashLife一样使用一些技巧，见1。

Answer 3

正如我在评论中所说，我相当确定您可以排除数组和 clone 操作。

您可以就地修改 StringBuilder，因此无需在 int[] 和 String 之间来回转换。

例如，（注意：这是对所有 T <= N 的 O(n) 操作的顺序）

public static void main(String[] args) {
    System.out.println(conway1d("0000001", 7, 1));
    System.out.println(conway1d("01011", 5, 3));
}

private static String conway1d(CharSequence input, int N, long T) {
    System.out.println("Generation 0: " + input);

    StringBuilder sb = new StringBuilder(input); // Will update this for all generations

    StringBuilder copy = new StringBuilder(); // store a copy to reference current generation
    for (int gen = 1; gen <= T; gen++) {
        // Copy over next generation string
        copy.setLength(0);
        copy.append(input);

        for (int i = 0; i < N; i++) {
            conwayUpdate(sb, copy, i, N);
        }

        input = sb.toString(); // next generation string
        System.out.printf("Generation %d: %s\n", gen, input);
    }

    return input.toString();
}

private static void conwayUpdate(StringBuilder nextGen, final StringBuilder currentGen, int charPos, int N) {
    int prev = (N + (charPos - 1)) % N;
    int next = (charPos + 1) % N;

    // **Exactly one** adjacent '1'
    boolean adjacent = currentGen.charAt(prev) == '1' ^ currentGen.charAt(next) == '1';
    nextGen.setCharAt(charPos, adjacent ? '1' : '0'); // set cell as alive or dead
}

对于您在评论中发布的问题中的两个示例，此代码生成此输出。

Generation 0: 0000001
Generation 1: 1000010
1000010
Generation 0: 01011
Generation 1: 00011
Generation 2: 10111
Generation 3: 10100
10100

O(log n) 编程

O(log n) Programming

java

algorithm

performance

processing-efficiency