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

Question

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

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

1. 这3个元素可以使用O(log²n)比较来确定。
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个变量中最小的一个，min₃是最大的一个），用列表的1^ST3个元素初始化它们，并扫描列表一次。对于列表中的每个数字x，我们有以下4种情况：

1. 如果x 1，则min ₃=min ₂；min ₂=min ₁；min ₁=x；
2. 否则，如果min₁ 2，则min ₃=min ₂；min ₂=x；
3. 否则，如果min₂ 3，则min ₃=x；
4. 否则，如果min₃

所以，基本上，在最坏的情况下，它需要3N个比较，在最好的情况下需要0个比较。

纠正我，如果它可以做一个其他更容易（更少的时间限制）的方式。实际上，我对选项3和4感到困惑。

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

1. 这两个元素可以使用O(log¹⁰⁰n)比较来确定。
2. O(log¹⁰⁰n)不够，但是可以使用n+O(logn)比较来确定它们。
3. n+O(logn)不够，但是可以使用3。ⁿ5₂比较来确定它们。
4. 3.ⁿ1/₂不够，但是可以使用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)中完成，方法是比较两个连续的元素，然后将较小的元素与当前最小的元素进行比较，将较大的元素与当前最大的元素进行比较。