如何在 O(k log n) 时间内搜索 n 个元素中的 k 个元素？
How do search k elements of n elements in O(k log n) time?
我的方法是 log n 意味着我们通过将数组分成 2 组来创建一棵树，直到我们将所有元素分开，然后我们将判断每个元素是否在数组中。
在这种方法中，时间复杂度应该是 O(n log n)，因为最后一个元素可能在最后一个叶子中。
我错过了什么？
我找到了解决方案，但我不明白。
二进制搜索使用该方法：
- 它以升序数组作为输入
- 转到中间元素
- 如果这就是您要查找的元素，那就是它
- 其他：
- 中间元素 < 搜索的元素 -> 使用数组右半部分作为输入数组的同一事物
- 中间元素 > 搜索的元素 -> 使用数组左半部分作为输入数组的同一事物
- 继续直到或找到元素，或数组大小为 1
如果数组未排序，您无法在 k*log n 中找到它，至少 O(n) 只需检查每个元素与所需的元素
您提供的解决方案不适用于您要解决的问题。在他们的背景下，他们可以测试某些城市组是否受到他们所谓的 "experiment" 污染，并且想知道他们需要多少实验才能准确找到哪些 k 城市受到污染.这是一种理论情况，很可能只是一种没有现实生活应用的练习。
实际上，在最坏的情况下，您无法在少于 O(n) 时间内测试数组是否包含元素，除非该数组具有某种结构（例如被排序）。特别是，您无法在 O(k log n) 时间内测试数组是否包含 k 个元素 k = o(n / log(n))，因为在这种情况下 k log n = o(n)。这当然也意味着常数k.
是不可能的
(但如果 k 与 n 的阶数相同，则 O(k log n) 变为 O(n log n) 然后你可以求助于对数组进行排序）。
如果您的数组已排序，那么您可以执行 k 二进制搜索并实现此运行时间。
我的方法是 log n 意味着我们通过将数组分成 2 组来创建一棵树，直到我们将所有元素分开，然后我们将判断每个元素是否在数组中。 在这种方法中，时间复杂度应该是 O(n log n)，因为最后一个元素可能在最后一个叶子中。 我错过了什么？ 我找到了解决方案，但我不明白。
二进制搜索使用该方法：
- 它以升序数组作为输入
- 转到中间元素
- 如果这就是您要查找的元素，那就是它
- 其他：
- 中间元素 < 搜索的元素 -> 使用数组右半部分作为输入数组的同一事物
- 中间元素 > 搜索的元素 -> 使用数组左半部分作为输入数组的同一事物
- 继续直到或找到元素，或数组大小为 1
如果数组未排序，您无法在 k*log n 中找到它，至少 O(n) 只需检查每个元素与所需的元素
您提供的解决方案不适用于您要解决的问题。在他们的背景下，他们可以测试某些城市组是否受到他们所谓的 "experiment" 污染，并且想知道他们需要多少实验才能准确找到哪些 k 城市受到污染.这是一种理论情况，很可能只是一种没有现实生活应用的练习。
实际上，在最坏的情况下，您无法在少于 O(n) 时间内测试数组是否包含元素，除非该数组具有某种结构（例如被排序）。特别是，您无法在 O(k log n) 时间内测试数组是否包含 k 个元素 k = o(n / log(n))，因为在这种情况下 k log n = o(n)。这当然也意味着常数k.
是不可能的(但如果 k 与 n 的阶数相同，则 O(k log n) 变为 O(n log n) 然后你可以求助于对数组进行排序）。
如果您的数组已排序，那么您可以执行 k 二进制搜索并实现此运行时间。