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

熊猫

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

我将不胜感激任何帮助。

朱维安

当前复杂度:

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

因此,当您更改一个元素时,您会中断循环以查找数字,然后不会中断 do while,因为预计数与计数不同。然后 allElementsEqual 函数运行,这也是 O(n)。因此,对于 do while 的每次运行,您执行两次 O(n) 操作。剩下的是循环运行时可以执行多少次。

它只能在所有元素都相等时停止,并且我们说在每一步中我们将 1 个数字与 num 接近 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)。如果我们在 do while 之外将 i 更改为 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) 中完成它并且不能做得更好,因为我们需要读取每个数字。所以这是最优的

本文收集自互联网,转载请注明来源。

如有侵权,请联系[email protected] 删除。

编辑于
0

我来说两句

0条评论
登录后参与评论

相关文章

来自分类Dev

计算内循环的时间复杂度

来自分类Dev

如何计算时间复杂度?

来自分类Dev

如何计算时间复杂度?

来自分类Dev

时间复杂度计算

来自分类Dev

循环的时间复杂度

来自分类Dev

循环的时间复杂度

来自分类Dev

3个嵌套循环的时间复杂度计算

来自分类Dev

c循环函数计算时间复杂度

来自分类Dev

计算嵌套循环在C中的时间复杂度

来自分类Dev

计算内部有循环的递归函数的时间复杂度

来自分类Dev

如果代码包含多个n个复杂度循环,如何计算复杂度?

来自分类Dev

如何计算DFS算法的时间复杂度?

来自分类Dev

如何计算冒泡排序时间复杂度

来自分类Dev

如何计算这段代码的时间复杂度?

来自分类Dev

如何计算递归函数的时间复杂度?

来自分类Dev

如何计算此算法的时间复杂度

来自分类Dev

如何计算此实现的时间复杂度

来自分类Dev

如何计算以下函数的时间复杂度?

来自分类Dev

如何计算这种递归方法的时间复杂度?

来自分类Dev

如何计算以下算法的时间复杂度

来自分类Dev

如何计算给定代码的时间复杂度?

来自分类Dev

如何计算此递归算法的时间复杂度

来自分类Dev

如何计算此算法的时间复杂度

来自分类Dev

如何计算此函数的时间复杂度?

来自分类Dev

如何计算我的C函数的时间复杂度

来自分类Dev

如何计算算法时间复杂度

来自分类Dev

如何计算这段代码的时间复杂度?

来自分类Dev

如何确定嵌套循环算法的计算复杂度?

来自分类Dev

如何找到嵌套for循环的时间复杂度