algorithm - 此K路径合并例程的运行时复杂度是多少？

这似乎是o（n log（k）），其中k是网格的宽度，n是深度（假设网格是平滑的，或者网格中的元素总数（如果网格是锯齿状的）。是这样吗？

public class KWayMerge {

  private int[] merge(int[][] grid) {
    return merge(grid, 0, grid.length - 1);
  }

  // O(n log k) wehre k is the width of the grid and n is the depth (assuming smooth grid)
  private int[] merge(int[][] grid, int start, int end) {
    if (end == start) {
      return grid[end];
    } else if (end - start == 1) {
      return merge(grid[end], grid[start]);
    } else {
      return merge(merge(grid, start, (end + start) / 2), merge(grid, ((end + start) / 2) + 1, end));
    }
  }

  private static int[] merge(int[] left, int[] right) {
    int[] result = new int[left.length + right.length];
    int lPos = 0, rPos = 0, pos = 0;
    while(true) {
      if (lPos >= left.length) {
        System.arraycopy(right, rPos, result, pos, right.length - rPos);
        break;
      } else if (rPos >= right.length) {
        System.arraycopy(left, lPos, result, pos, left.length - lPos);
        break;
      }

      if (left[lPos] < right[rPos]) {
        result[pos] = left[lPos];
        lPos++;
      } else {
        result[pos] = right[rPos];
        rPos++;
      }

      pos++;
    }

    return result;
  }
}

最佳答案

你的复杂性（O）
例如，您有8个大小为n的数组：
您将有以下合并：
迭代1：
12（2*N）
34（2*N）
56（2*N）
78（2*N）
迭代2：
1234（4*N）
5678（4*N）
迭代3：
一12345678（8*N）
完全地：
你有以下的复杂性
K/2*（2*N）
K/4*（4*N）
K/8*（8*N）
然后分别为K*N和LogK count。
总复杂度为o（千分之十六）
其中K个数组计数，N是数组的平均大小。