是否可以将嵌套循环替换为计数器变量以降低时间复杂度？

Question

这可能是一个新手问题，但我有一个使用嵌套循环在二维数组中查找值的方法，假设正文看起来像这样：（假设在二维数组中总是有一个匹配项 1）


        // example array ==> int arr = new int[5][5]
        int length = arr.length;
        int index1 = -1;
        int index2 = -1;

        loop:
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                if (arr[i][j] == 1) {
                    index1 = i;
                    index2 = j;
                    break loop;
                }
            }
        }

我以这种方式用额外变量 (counter) 替换了第二个循环：

        // example array ==> int arr = new int[5][5]
        int length = arr.length;
        int index1 = -1;
        int index2 = -1;
        int counter = 0;

        for (int i = 0; i < length; i++) {
            if (arr[counter][i] == 1) {
                index1 = counter;
                index2 = i;
                break;
            }

            if (i == length - 1) {
                counter++;
                i = 0;
            }
        }

这仍然被认为是具有相同时间复杂度的嵌套循环吗？并且如果有好的link可以理解如何从总体上分析我的代码复杂度，请附上！

这是一个示例代码，我知道可以做一些改进，但我只是问时间复杂度（忽略边缘情况和错误处理）

Answer 1

它认为O()的内容是执行所需的最大操作数和'n'参数来标识输入的大小。

for 循环通常迭代一定大小，在本例中就是数组的大小。

一个 for 循环因此最多执行 'n' 个操作，这就是为什么它被称为线性时间或 O(n)。

在第一种情况下，您显示了两个嵌套的 for 循环，在这种情况下，必须进行简单的乘法运算，因为复杂度 O(n) 的循环最多完成 'n' 次，所以它称为二次时间或 O(n^2).

O(n)的值越大，复杂度越大

为简单起见：

For循环是O(n)并且没问题
2+ 对于非嵌套循环是 O(n+n)，但它仍然说 O(n) 没关系
2 对于嵌套循环是 O(n*n) 并且不好
3 对于嵌套循环是 O(nnn) 并且非常糟糕

这就是为什么你发送的第二个代码，假设没有错误，肯定比第一个更快。

Answer 2

您应该将此条件添加到 for 循环中，否则您将遇到 ArrayOutOfBoundException：

 for (int i = 0; i < length && counter < length-1; i++) //if the array is something like new int[5][5]

尝试使用 currentTimeMillis() 测量两者的执行时间，使用不同的数组和迭代:)

Answer 3

您可以使用测试应用来检查每种方法的性能，如下面的代码片段

package test;

public class TestLoops {

    static int numOfItrr = 30000;
    static int[][] arr = new int[numOfItrr][numOfItrr];

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        initArr();

        System.out.println("=====================Start======================");
        System.out.println("numOfItrr :" + numOfItrr);
        initArr();
        testWithForLoops();
        testWithCounter();
        System.out.println("=====================Finish=====================");
    }

    public static void initArr() {
        for (int i = 0; i < numOfItrr; i++) {
            for (int j = 0; j < numOfItrr; j++) {
                arr[i][j] = (int) (Math.random() * 1000);
            }
        }
    }

    public static void testWithForLoops() {
        long start = System.nanoTime();
        int max = arr[0][0];

        for (int i = 0; i < numOfItrr; i++) {
            for (int j = 0; j < numOfItrr; j++) {
                if (arr[i][j] > max) {
                    max = arr[i][j];
                }
            }
        }

        long end = System.nanoTime();
        System.out.println("time With loops    = " + (end - start));

    }

    public static void testWithCounter() {
        long start = System.nanoTime();

        int counter = 0;
        int max = arr[0][0];

        for (int i = 0; i < numOfItrr; i++) {
            if (arr[counter][i] > max) {
                max = arr[counter][i];
            }
            if (i == numOfItrr - 1 && counter < numOfItrr - 1) {
                counter++;
                i = 0;
            }
        }

        long end = System.nanoTime();
        System.out.println("time With Counter  = " + (end - start));
    }

}

这是示例结果

====================开始=====================

数量：10000

循环时间 = 86591300

计数器时间 = 110362600

====================完成=====================

====================开始=====================

数量：30000

循环时间 = 754436400

使用计数器的时间 = 978285600

====================完成=====================

====================开始=====================

数量：30000

循环时间 = 754230300

使用计数器的时间 = 970180300

====================完成=====================

Answer 4

你的两个解的时间复杂度是一样的

有些人犯了只计算循环次数的错误。因此，如果只有一个可识别的循环，他们会说这是一种线性算法。但事实并非如此，它仍然是二次方的。你要检查的是重复的操作重复了多少次。

在这种情况下，让我们专注于比较（将数组值与 1 进行比较）。这是重复次数最多的操作（您可以自己验证），因此它重复的次数与 N（数组一维的大小，意味着数组本身是 NxN）成正比，这决定了大 O。

因此，在您的第一个双循环示例中，每次执行内部循环时，都会进行 N 次比较。由于外循环，内循环本身重复了 N 次，因此你有 NxN 次比较，最后得到 O(N²)。

在您的第二个单循环示例中，比较执行的迭代次数与循环一样多。假设最坏的情况，1 在最后一个单元格中，这里会发生什么？每次到达一行的末尾时，都会重置 i。所以你又开始从 0 数到 N-1。因此，您对 counter = 0 进行了 N 次比较，然后对 counter = 1 进行了 N 次比较，依此类推，直到 counter 达到 N-1。因此，您再次进行了 NxN 次比较，因此 O(N²)。

所以检查循环只是一个经验法则。您真正应该计算的是 operations.

是否可以将嵌套循环替换为计数器变量以降低时间复杂度？

Could a nested loop be replaced with a counter variable to reduce the time complexity?

java

big-o

loops

nested

time-complexity