gpt4 book ai didi

algorithm - 合并 K 个排序链表,为什么复杂度是 O(N * K * K),而不是 O(N * K)

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:37:57 28 4
gpt4 key购买 nike

我有以下解决方案,但我从其他评论者那里听说它是 O(N * K * K),而不是 O(N * K)其中 NK 列表的(最大)长度,K 是列表的数量。例如,给定列表 [1, 2, 3][4, 5]N 是 3 而 K 是 2。

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
private void advance(final ListNode[] listNodes, final int index) {
listNodes[index] = listNodes[index].next;
}

public ListNode mergeKLists(final ListNode[] listNodes) {
ListNode sortedListHead = null;
ListNode sortedListNode = null;

int associatedIndex;

do {
int minValue = Integer.MAX_VALUE;
associatedIndex = -1;

for (int listIndex = 0; listIndex < listNodes.length; listIndex++) {
final ListNode listNode = listNodes[listIndex];

if (listNode != null && listNode.val < minValue) {
minValue = listNode.val;
associatedIndex = listIndex;
}
}

if (associatedIndex != -1) {
if (sortedListNode == null) {
sortedListNode = new ListNode(minValue);
sortedListHead = sortedListNode;
}
else {
sortedListNode.next = new ListNode(minValue);
sortedListNode = sortedListNode.next;
}

advance(listNodes, associatedIndex);
}
}
while (associatedIndex != -1);

return sortedListHead;
}
}

我的推理是 do-while 循环的主体将出现 N 次(因为 do-while 循环的停止条件是当最长的列表已被迭代时完成),而 do-while 循环的 for 循环体将出现 K 次(listNodes .length),产生 O(n * k)

为什么上面的解是O(n * k * k)呢?

最佳答案

您的结果列表将最多包含 n * k 个项目。添加每一项的成本为 O(k)(内部循环执行 k 迭代以检查每个列表的头部)。因此,总运行时间为 O(n * k * k)。

关于algorithm - 合并 K 个排序链表,为什么复杂度是 O(N * K * K),而不是 O(N * K),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53454615/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com