在小于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. 以上都不是.

在这里,我想它的方式是采取3个变量(如:MIN ₁,MIN ₂和MIN ₃,其中MIN ₁是最小和最小值,₃是最大的,这些3),与1个初始化它们^ST的3个要素列表并扫描列表一次.对于列表中的每个数字x,我们有以下4种情况:

1. 如果 x <最小₁ 那么,最小₃ =最小₂ ; 最小₂ =最小₁ ; 最小₁ = x;
2. 否则如果 Min ₁ <x <Min ₂ 则 Min ₃ = Min ₂ ; 最小₂ = x;
3. 否则如果 Min ₂ <x <Min ₃ 则 Min ₃ = x;
4. 否则如果 Min ₃ <x 那么,什么也不做

所以,基本上它会要求在最坏的情况下3N比较,并在最好的情况下0比.

如果可以以更简单(更少时间限制)的方式完成,请纠正我.实际上我对选项3和4感到困惑.

问题2

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

1. 这两个元素可以使用O(log ¹⁰⁰ n) 比较来确定.
2. O(log ¹⁰⁰ n)不够,但可以使用n + O(logn)比较来确定它们.
3. N + O(logn)时间是不够的,但是它们可以使用被确定3.⌈ ^ñ/₂ ⌉比较.
4. 3.⌈ ^Ñ/₂ ⌉是不够的,但它们也可以利用来确定2(N-1)的比较.
5. 以上都不是.

像以前一样使用类似的参数我得出了答案2(n-1).虽然我仍然对选项2和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) 中完成，方法是比较两个连续的元素，然后将较小的元素与当前的最小值进行比较，将较大的元素与当前的最大值进行比较。