具有两个变量的时间复杂度单循环

Question

下面代码的时间复杂度是多少？为什么？

public static int[] Shuffle(int[] nums, int n)
{
    int len = nums.Length;
    int[] final = new int[2 * n];
    int counter = 0;
    for (int i = 0, j = n; i < n; i++, j++)
    {
        final[counter++] = nums[i];
        final[counter++] = nums[j];
    }

    return final;
 
}

如果我们有如下两个循环那么它将被认为是 O(n^2)

的时间复杂度

for (int i = 0; i < n; i++)
{
   for (int j = 0; j < n; j++)
   {
   }
}

Answer 1

复杂度为 O(n)，因为游标从 i = 0 循环到 i = n-1。就时间复杂度而言，变量的数量无关紧要。（也有 space 复杂性）但是要小心，

for (int i = 0, j = n; i < n; i++, j++)

完全不同于

for (int i = 0; i < n; i++)
{
   for (int j = 0; j < n; j++)
   {

具有两个变量的时间复杂度单循环

Time complexity single loop with two variables

time-complexity

data-structures