complexity-theory - 代码的时间复杂度和数量级的改进

Question

我有以下问题：

1. 对于下面的代码，有理由地给出函数的时间复杂度。

2. 编写一个执行相同任务但时间复杂度提高一个数量级的函数。具有更大（时间或空间）复杂性的功能将不会获得信任。

代码：

int something(int[] a) {
    for (int i = 0; i < n; i++)
        if (a[i] % 2 == 0) {
             temp = a[i];
             for(int j = i; j > 0; j--)
                a[j] = a[j-1];
             a[0] = temp;
        }
}

我在想，由于temp = a[i]在最坏情况下的分配是完成n时间，时间复杂度n被分配给它，并且a[j] = a[j-1]是运行n(n+1)/2时间，所以时间复杂度值被分配给它，将它们相加返回时间复杂度，删除常数将导致和 的复杂性。(n2+n)/2n+0.5n2+0.5n2n+n2n2

对于数量级的改进：

int something(int[] a) {
    String answer = "";
    for (int i = 0; i < n; i++) {
       if (a[i] % 2 == 0) answer = a[i] + answer;
       else answer = answer + a[i];
    }
    for (int i = 0; i < n; i++)
       a[i] = answer.charAt(i);
}

第一个 for 循环内的代码执行n次数，在第二个 for 循环n次数中，求和给出的时间复杂度为2n.

这个对吗？还是我做错了什么？

Answer 1

我想你的功能是在列表的开头排列一个包含所有偶数的列表，然后是奇数。

对于第一个函数，复杂度为您指定的O(n ² ) 。

但是对于第二个函数，如果用于追加的运算符被实现为常数时间运算，则复杂度为O(n) 。+通常追加操作符+被实现为一个恒定时间操作，没有任何隐藏的复杂性。因此我们可以得出结论，第二次操作需要O(n)时间。