在k <n的算法运行时log（n）vs log（k）

Question

复杂性分析中，我无法理解log（k）和log（n）之间的差异。

我有一个大小为n的数组。我有另一个数字k < n是算法的输入（所以它不是提前知道的常数）。什么是算法的一些例子会有log（n）与那些log（k）的复杂度的算法？我只能想到复杂度为log（n）的算法。

例如，mergesort在其运行时分析（O（nlogn））中具有log（n）复杂性。

Answer 1

如果您的算法利用大小n的列表和一些大小k < n，输入大小是n + log(k)的顺序（假设k可以是的n相同渐近量级）上。为什么？ k是以地点价值系统（例如，二进制或十进制）表示的数字，并且要求数字的数量级别为log k数字来表示。因此，如果您的算法采用输入k并以需要使用或检查其所有数字的方式使用它（例如，正在检查相等性等），那么整个算法的复杂度至少为订单号为log k。如果你用数字做更复杂的事情，复杂性可能会更高。例如，如果您有类似for i = 1 to k do ...的东西，则算法的复杂度至少为k - 可能会更高，因为您正在比较log k位数k次（尽管i对于许多/大多数值使用的位数少于k的i，根据基地）。

Answer 2

关于O（log k）项可能出现在哪里，没有“一刀切”的解释。

您有时会看到此运行时出现在搜索和排序算法中，您只需重新排列序列的一小部分。例如，C++标准库的std::partial_sort函数重新排列序列，以便前k个元素按排序顺序排列，其余元素在时间O（n log k）中以任意顺序排列。实现这一点的一种方式是维持大小至多为k的最小堆和做Ñ插入/缺失就可以了，这是n个操作，每个需要时间为O（log K）。同样，有一个O（n log k）时间算法用于查找数据流中的k个最大元素，该算法通过维护最多k个元素的最大堆积来工作。 （这两种方法都不是最优的 - 但你可以使用线性时间选择算法在时间O（n + k log k）上进行部分排序，并且可以类似地找到数据流的前k个元素O（N）。）M

也有时会看到这种运行在涉及分而治之的策略，其中所涉及的问题的大小取决于输入大小的一些参数的算法。例如，Kirkpatrick-Seidel algorithm用于计算凸包确实每级线性工作在复发，和层的数量是为O（log k），其中k是在所得到的凸壳元件的数量。总的工作是O（n log k），使其成为输出敏感的算法。

在一些情况下，一个为O（log K）可出现术语，因为要处理的元件一位数字时间的集合。例如，radix sort为O的运行时间用于排序了n后（N日志k）的范围从0到K，以下，与所述日志ķ术语的事实，有为O（log K）的数字出现在数值ķ。

在图算法中，边​​数（m）与节点数（n）有关但可以独立于节点数（n），您经常会看到像O（m log n）这样的运行时，就像您implement Dijkstra's algorithm with a binary heap。