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

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)是更新每个元素descrease它归结为成本num。

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