Определение временной сложности слияния K отсортированных массивов

Question

Я написал Merge K Sorted Arrays. Я обнаружил, что наилучшая временная сложность для этого времени равна O (n k Logk) на других сайтах, где k - это число массивов, а n - количество элементов в каждом массиве. Я думаю, что мой O (n k).

Кто-нибудь может это подтвердить ?? Код ниже.

private static void MergeKSortedArrays()
{
    int[][] arr = { new int[] { 3, 5, 7 }, new int[] { 1, 2, 4 }, new int[] { 6, 8, 9 } };
    int k = 3, n = 3;

    int[] output = new int[n * k];
    int[] temp = new int[k];

    for (int i = 0; i < k - 1; i++)
    {
        temp = Merge(arr[i], arr[i + 1]);  // takes Linear time
        arr[i + 1] = temp;
    }

    foreach(int i in arr[k-1])
    {
        Console.Write(i + " ");
    }
    Console.WriteLine();

}

private static int[] Merge(int[] a, int[] b)
{
    int[] o = new int[a.Length + b.Length];
    int i = 0, j = 0, ind = 0;

    for (; i < a.Length && j < b.Length;)
    {
        if (a[i] <= b[j])
        {
            o[ind] = a[i];
            i++;
            ind++;
        }
        else
        {
            o[ind] = b[j];
            j++;
            ind++;
        }
    }

    if (i < a.Length)
    {
        for (; i < a.Length; i++, ind++)
        {
            o[ind] = a[i];
        }
    }
    else if (j < b.Length)
    {
        for (; j < b.Length; j++, ind++)
        {
            o[ind] = b[j];
        }
    }

    return o;
}

Answer 1

Нет.

В первой итерации вы объединяете массив длины n с массивом длины n

Во второй итерации вы объединяете массив длиныn с массивом длиной 2n

В третьей итерации вы объединяете массив длины n с массивом длины 3n

...

Это означает цикл forв вашем методе Merge () будет выполняться 2n + 3n + 4n ... = (k+1)*k/2 * n -1 раз.

Таким образом, предлагаемый вами алгоритм на самом деле O(n * k^2)