algorithm - 在小于 O(n) 的比较中找到 3 个最小元素的时间复杂度

Question

关于确定 2 种算法的时间复杂度，我有 2 个问题。

问题1

使用比较从一组 n 不同 数字中确定最小的 3 个数字。

1. 可以使用O(log²n) 比较来确定这 3 个元素。
2. O(log²n) 还不够，但是可以使用 n + O(1) 比较来确定它们。
3. n + O(1) 还不够，但是可以使用 n + O(logn) 比较来确定它们。
4. n + O(logn) 还不够，但是可以使用 O(n) 比较来确定它们。
5. 以上都不是。

Here, the way I thought of it is to take 3 variables (e.g: MIN₁, MIN₂ & MIN₃ where MIN₁ being the smallest & MIN₃ being the largest of these 3), initialize them with the 1^st 3 elements of the list and scan the list once. For each number x in the list we have the following 4 cases:

1. if x < Min₁ then, Min₃ = Min₂; Min₂ = Min₁; Min₁ = x;
2. else if Min₁ < x < Min₂ then, Min₃ = Min₂; Min₂ = x;
3. else if Min₂ < x < Min₃ then, Min₃ = x;
4. else if Min₃ < x then, do nothing

So, basically it'll require 3n comparisons in the worst case and 0 comparison in the best case.

Correct me if it can be done in an otherwise easier (less time bound) way. Actually I'm confused with options 3 and 4.

问题2

使用比较从一组 n 不同 数字中确定最小和最大数字。

1. 这 2 个元素可以使用 O(log¹⁰⁰n) 比较来确定。
2. O(log¹⁰⁰n) 还不够，但是可以使用 n + O(logn) 比较来确定它们。
3. n + O(logn) 还不够，但是可以使用 3.⌈ⁿ⁄₂ 来确定它们⌉ 比较。
4. 3.⌈ⁿ⁄₂⌉ 还不够，但是可以使用 2.(n- 1)比较。
5. 以上都不是。

Using analogous argument as before I've come up with the answer 2(n-1). Although I'm still confused between options 2 and 4.

Answer 1

问题 1: 您可以通过首先与 MIN2 进行比较来改进您的算法以进行 2n 次比较。这仍然是 O(n)。 要看出 n+O(1) 是不够的，请注意存在 n*(n-1)*(n-2) 种可能性，其中 MIN1、MIN2 和 MIN3 位于其中。 取以 2 为底的对数以获得所需比较次数的下限。

问题 2: 这可以在 3*ceil(n/2) 中完成，方法是比较两个连续的元素，然后将较小的元素与当前的最小值进行比较，将较大的元素与当前的最大值进行比较。