将 k 个新元素插入已经包含 n 个元素的二进制堆的时间复杂度是多少？我有一个约束，我需要以 0(k + Log n) 复杂度插入 k 个元素。
提示：使用类似于堆构建的自底向上方法。
问问题
1562 次
1 回答
0
这个问题没有简单的答案。
二叉堆插入的平均复杂度为O(1)，最坏情况为O(log N). 复杂度将保持在该范围内k，但完成操作所花费的实际时间（不是时间复杂度；我相信您可能会混淆这些术语）将取决于实现、平台和风向。
就时间而言，与具体答案最接近的是，插入元素所花费的时间最多与从到积分k成线性比例，k在最坏的情况下与积分成比例。对于明显大于我们可以近似成比例的时间。log (x)Nk+NNkk log N
有关更多信息，请参阅：http ://en.wikipedia.org/wiki/Binary_heap
于 2014-05-08T10:54:13.913 回答