如果我们有一个无序列表有 n 个不同的元素，那么现在我对时间复杂度是 ϴ(n) 还是 ϴ(1) 感到困惑，因为在最坏的情况下我们可能最终会进行 n 次比较，但是如果我采取一次3个元素然后我可以在ϴ(1)时间内找到第二大元素，所以我对这两种方法感到困惑，请指导。
最佳答案
这很简单:
第一种方法有很多完全无用的开销。由于列表仅包含不同的项目，前三项中的一项必须满足既不是列表中最大元素也不是最小元素的约束。对于查找与约束条件匹配的任意元素而言，所有其他比较都是完全无用的。
关于algorithm - 在无序列表中找到一个既不是最大也不是最小值的元素需要多少次比较？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34551456/