时间戳

首页 > 解决方案 > 如何计算肯定会在某个点结束的无限循环的时间复杂度？

java - 如何计算肯定会在某个点结束的无限循环的时间复杂度？

问题描述

所以我有以下代码，首先我使用 a while(true)with 使用具有相同条件的语句来破坏它，该if语句现在在我的do-while循环中。

代码现在如下所示：

do {
        for (int i = 0; i < arrayToUse.length; i++) {
            int diff = arrayToUse[i] - number;

            if (diff >= 5) {
                arrayToUse[i] -= 5;
                count++;
                break;
            }

            if (diff >= 2) {
                arrayToUse[i] -= 2;
                count++;
                break;
            }

            if (diff == 1) {
                arrayToUse[i] -= 1;
                count++;
                break;
            }
        }

        if(preCount == count)
            break;

        preCount = count;

    } while (!allElementsEqual(arrayToUse, number));

这arrayToUse是我收到的输入数组。的代码allElementsEqual()如下所示：

static boolean allElementsEqual(int[] arr, int num){

    for(int i=0;i<arr.length;i++){
        if(arr[i] != num)
            return false;
    }

    return true;
}

我在使用它的代码中有超时，并且我无法找到如何计算尚未明确定义结束时间的算法的时间复杂度。我说的是 Big Oh Notation 中的时间复杂度。

我将不胜感激任何帮助。

标签： javaalgorithmtime-complexityinfinite-loop

解决方案

当前复杂性：

让我们称 m 为数组的最大数量。您的第一个循环将最多运行 N 次以找到仍然大于 num 的数字。当它这样做时，它会使其更接近 num 最多 5 个单位。2 和 1 单元对于复杂性并不重要，但重要的部分是它总是会使它更接近 num。

所以当你改变了一个元素时，你打破循环来找到数字，然后不会打破do while，因为预计数将与计数不同。然后 allElementsEqual 函数运行，这也是 O(n)。因此，对于 do while 的每次运行，您执行两次 O(n) 操作。剩下的就是while循环运行多少次了。

它只能在所有元素相等时停止，并且我们说过在每一步中我们使 1 个数字更接近 num 最多 5。这意味着对于我们数组中的每个数字，它将运行大约 ((originalNumber[i] - num) / 5) 次，最坏的情况是最大值，即 m。因此，大约需要 (m - num) / 5 次循环才能使该数字等于 num。如果所有数字都是最大值，这意味着对于每个数字，我们将执行 (m - num) / 5 步以使其等于 num。

这为每个数字提供了 (m - num) / 5 个步骤，有 N 个数字，每个步骤花费 O(n)，总而言之，复杂度为 O((m - num) / 5 * N * N)。我们可以删除 /5 并将其保留为 O((m - num) * N * N)。

附带说明一下，使用 while(true) 而不是 allElementsEqual 是相同的，因为您的 precount == count if 已经在负责检查。

我们能做得更好吗？

假设我们删除 allElementsEqual 为真，这会将操作更改为 O(1) 而不是 O(n)，但我们仍然有循环来找到不等于 num 的数字，即 O(n)。如果我们将 i 更改为在 do while 之外初始化为 0，以便它不会在每一步都从 0 开始，它会将操作更改为 O(1) 并且仍然有效，因为中断会阻止 i 更新，直到差异为 0，当差异为 0 时，我们不再关心该数字，因此我们可以增加 i。这将算法更改为 O((m - n) * N)

我们还能做得更好吗？

与其用最多 5 个单位使数字更接近 num，我们为什么不一次全部完成呢？我们可以计算需要减少 5 次，减少 2 次（0、1 或 2 次）和 1 次（0 或 1 次）的次数。

int diff = arrayToUse[i] - number;

count += floor(diff / 5) + floor((diff % 5) / 2) + (diff % 5) % 2
arrayToUse[i] = number;

有了这个，我们可以在 O(N) 中做到这一点，并且不能做得更好，因为我们需要读取每个数字。所以这是最优的

推荐阅读