如何计算确定在某一点结束的无限循环的时间复杂度？

Question

所以我有以下代码，首先我使用 while(true) 并使用 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 中的时间复杂度。

如有任何帮助，我将不胜感激。

Answer 1

我会说 O(n² + n*m)，其中 n 是 arrayToUse 的长度，m 是数组中包含的最大值。

在最坏的情况下，您将不得不运行主循环 n 次来更改每个元素并使其等于 num，因为每个运行似乎能够同时更新一个元素。所以我们有一个外部n倍增因子。

然后我们有每个循环的成本，这似乎是 O(n + m)，因为 O(n) 是测试的成本，O(m) 是更新每个元素的成本将它减少到 num.

所以O(n² + n*m).

Answer 2

当前复杂度：

我们称m为数组的最大数。你的第一个循环将运行至多 N 次以找到仍然大于 num 的数字。当它这样做时，它最多会在 5 个单位内更接近 num。 2和1的单位对于复杂度来说并不重要，重要的是它总是会让它更接近num。

因此，当您更改了一个元素时，您打破循环以查找数字，然后不会打破 do while，因为 precount 将不同于 count。然后是 allElementsEqual 函数运行s，这也是 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 为 true，这会将操作更改为 O(1) 而不是 O(n)，但我们仍然有循环来查找不等于 num 的数字，即 O(n)。如果我们将 i 更改为在 do while 之外初始化为 0，这样它就不会在每一步都从 0 开始，它将操作更改为 O(1) 并且仍然有效，因为中断将阻止 i 更新直到差异为 0，当差异为 0 时，我们不再关心该数字，因此我们可以增加 i。这会将算法更改为 O((m - n) * N)

我们可以做得更好吗？

与其让数字更接近 num 最多 5 个单位，不如一次全部完成？我们可以计算需要减少 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) 内完成，并且不能做得更好，因为我们需要读取每个数字。所以这是最优的

如何计算确定在某一点结束的无限循环的时间复杂度？

How to compute time complexity of an infinite loop which is sure to end at a point?

java

algorithm

infinite-loop

time-complexity