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

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

当前复杂度:

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

因此，当您更改了一个元素时，您会中断循环以查找数字，然后不会中断 do while，因为 precount 与 count 不同。然后运行 ​​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 为 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) 内完成，而且做得更好，因为我们需要读取每个数字。所以这是最优的