java - O(log n) 编程

Question

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

例如，

如果您有一个包含 0 和 1 的整数数组，例如 [ 0, 0, 0, 1, 0, 1 ]，现在您想用 1 替换每个 0 只有当其中一个是邻居时 的值为 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

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

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

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

您还可以使用一些技巧作为 HashLife，参见 1 .