时间戳

首页 > 解决方案 > 在单循环有序列表中插入 M 个元素的时间复杂度是多少？

linked-list - 在单循环有序列表中插入 M 个元素的时间复杂度是多少？

问题描述

On a singly circular ordered list having N elements and 
if M elements are to be inserted what will be the complexity of time?


a) O(M*N)

b) O(M*(M+N))

c) O((M+N) * log(M+N))

我认为，完成这项工作所花费的时间应该是O(N + M). 因为我们需要O(N)找到最后一个元素并O(M)在其后插入所有元素，链接将采用O(1).

另外，我觉得这个词Ordered有点令人困惑，是它Sorted还是Preserving Natural Ordering.

如果Ordered意味着Preserving Natural Ordering那么我认为O(N + M)。

如果Sorted那时O(N * M)

标签： linked-listtime-complexityinsertioncircular-list

解决方案

这看起来像是一个排序的情况，而不是“保留自然排序”，我们将计算插入的完整操作（所有 m 个元素）的频率，因此如果我们假设值为N 比 M 高得多

推荐阅读