按给定顺序创建目标数组的算法的时间复杂度

Question

该算法的时间复杂度是多少?

public int[] createTargetArray(int[] nums, int[] index) {
int[] target = new int[nums.length];
int i = 0, k = 0;
while (i < index.length) {
for (k = target.length - 1; k > index[i]; k--)
target[k] = target[k - 1];
target[index[i]] = nums[i];
i++;
}
return target;
}

我已经提供了输入/输出，并在下面给出了解释。

Input: nums = [0,1,2,3,4], index = [0,1,2,2,1]
Constraint: nums.length == index.length
Output: [0,4,1,3,2]
Explanation:
nums       index     target
0            0        [0]
1            1        [0,1]
2            2        [0,1,2]
3            2        [0,1,3,2]
4            1        [0,4,1,3,2]

根据我的理解，while环占用O(n)时间，for内环也占用O(n)时间。这个方案的时间复杂度是O(n^2)吗?如果我说错了，请纠正我。

Answer 1

TL;DR更准确地说，如果我们假设m = n，则复杂度为O(n * m),O(n^2);

根据我的理解，while循环需要O(n)时间内部for循环也需要O(n)。它的时间复杂度是多少解决方案O (n ^ 2) ?

首先让我们将代码重写为:

public int[] createTargetArray(int[] nums, int[] index) {
int[] target = new int[nums.length];
for (int i = 0; i < index.length; i++) {
for (int k = target.length - 1; k > index[i]; k--)
target[k] = target[k - 1];
target[index[i]] = nums[i];
}
return target;
}

第一个循环从i = 0迭代到index.length，在最坏的情况下(即:，index[i]为零)从k = target.length - 1到k = 1的第二次循环迭代。因此，n开始表示数组index中的元素数，m开始表示数组num中的元素数。该算法的时间复杂度为O(n * m)。

如果一个人假设m = n，那么他可以说O(n^2)。

Answer 2

是的，时间复杂度是O(n^2)外部while循环执行n步骤，这很清楚，内部for循环依赖于index[]数组的项。假设其中所有的项目都是0那么内部循环将始终运行n-1步骤所以时间复杂度将是n*(n-1)因为我们考虑的是大0表示法，因此O(n^2)