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

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/output 及其解释如下。

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

是的，时间复杂度为 O(n^2) 外部 while 循环采取 n 步，这很清楚，内部 for 循环取决于 index[] 数组的项目。假设所有项目都在其中 0 然后内部循环将始终运行 n-1 步骤所以时间复杂度将是 n*(n-1) 这是 n*n 因为我们正在考虑大 O 符号，因此 O(n^2)

Answer 2

TL;DR 如果我们假设 m = n;

更准确地说，复杂度是 O(n * m), O(n^2)

According to my understanding, the while loop takes O(n) time and the inner for loop also takes O(n). Is the time complexity of this solution 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).

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

Time complexity of my algorithm for creating a target array in the given order

algorithm

math

complexity-theory

big-o

time-complexity