问如何计算此code?=.=的时间复杂度

EN

时间复杂性是衡量程序的运行时如何随着输入大小的增长而变化的指标。首先，您必须确定输入的哪个方面(如果有的话)会导致运行时发生变化，并将该方面表示为变量。将运行时设置为该变量(或这些变量)的函数是确定程序时间复杂性的方法。通常，当输入的单个方面导致运行时间发生变化时，我们用变量n表示这个方面。

您的程序主要根据for循环运行次数的不同而在运行时发生变化。我们可以看到for-循环运行chars时间的长度(注意，字符的长度是num的数字数)。方便地，该长度已经表示为n，我们将使用它作为表示输入大小的变量。也就是说，取n作为num中的数字数，我们希望通过将运行时表示为n的函数来精确地确定运行时随n的变化。

还请注意，在进行复杂性分析时，您主要关注的是运行时的增长，因为n变得任意大(当n到无穷大时是如何运行的)，所以您通常忽略常数因子，只关注最高阶项，用"大O“符号编写运行时。也就是说，由于3n、n和n/2都以与n走向无穷大的方式生长，所以我们将它们全部表示为O( n)，因为我们的主要目标是将这种线性增长与n^2、5n^2 + 10或n^2 +n的二次增长从log(n)、log(2n)或log(n) + 1的对数O(logn)增长或常数O( 1 )时间(不与n进行缩放的时间)区分开来。

所以，让我们试着用n来表示这个程序所做的操作的总数。首先，对它进行逐行处理并在最后将所有的操作加起来是有帮助的。

第一行将num转换为n字符串，然后将该字符串转换为字符的长度n数组，这是O(n)所做的工作。(n将n个数字中的每一个转换为一个字符，而另一个n个将其中的每个字符转换为一个数组。N+n= 2n = O(n)总功)

char[] chars = String.valueOf(num).toCharArray(); // O(n)

下一行只读取数组中的长度值，并将其保存为n。无论数组的长度如何，此操作所需的时间都是相同的，因此它是O(1)。

int n = chars.length; // O(1)

对于num的每一个数字，我们的程序运行1 For循环，所以O(n)总循环：

for (int i = n - 1; i > 0; i--) { // O(n)

在for循环中，执行条件检查，如果返回true，则可能会减少值并填充从i到n的数组。

        if (chars[i - 1] > chars[i]) {     // O(1)
            chars[i - 1]--;                // O(1)
            Arrays.fill(chars, i, n, '9'); // O(n-i) = O(n)
        }

填充操作是O(N)，因为这是多少字符可以更改为'9‘。O ( n )是O(n)，因为我只是一个常数和低阶，正如前面提到的，这意味着它在大O中被忽略了。

最后，将chars的n字符解析为int，并返回它。共：

static Integer foo(int num) {
    char[] chars = String.valueOf(num).toCharArray(); // O(n)
    int n = chars.length;                             // O(1)
    for (int i = n - 1; i > 0; i--) {  // O(n)
        if (chars[i - 1] > chars[i]) {     // O(1)
            chars[i - 1]--;                // O(1)
            Arrays.fill(chars, i, n, '9'); // O(n)
        }
    }
    return Integer.parseInt(new String(chars)); // O(n)
}

当我们把所有的东西加起来，我们得到，总时间复杂度是n，T(n)的函数。

T(n) = O(n) + O(1) + O(n)*(O(1) + O(1) + O(n)) + O(n)

表达式中有一个乘积，用于表示for-循环的所有迭代所做的全部工作: O(n)迭代次数为O(1) + O(1) + O(n)工作。实际上，有些迭代for循环可能只执行O(1)工作(当条件为false)，但在最坏的情况下，每次迭代都执行整个系统，除非另有规定，复杂性分析通常是针对最坏的情况进行的。

通过使用大O条常数和低阶项，以及O(a) + O(b) = O(a + b)和a*O(b) = O(a*b)的事实，可以将这个函数简化为运行时。

T(n) = O(n+1+n) + O(n)*O(1 + 1 + n) 
     = O(2n+1) + O(n)*O(n+2)
     = O(n) + O(n)*O(n)
     = O(n) + O(n^2)
     = O(n^2 + n)
     = O(n^2)

所以你会说，程序的总体时间复杂度是O(n^2)，这意味着在最坏的情况下，运行时间尺度与输入大小成二次。