所有搜索算法的Big-Omega时间复杂度均为O(1)是否正确？

• 首先明确：你说线性搜索的Big-Omega是Ω(1)在特定场景下是正确的——当目标元素恰好是数组第一个元素时，算法只需要1次比较就完成，这属于最佳情况输入的时间下界，确实满足Ω(1)的定义（存在常数c=1，n0=1，当n≥1时，运行时间≥1*1）。

• 但资料里说线性搜索的Big-Omega是Ω(n)，指的是算法的紧下界（最坏情况的下界）：当目标元素不存在于数组中时，线性搜索必须遍历完整个n个元素才能得出结论，这种情况的运行时间是Ω(n)。而我们谈论算法的Big Ω复杂度时，通常默认指的是所有可能输入下的“固有下界”——也就是存在无穷多输入需要算法花费至少Ω(n)的时间，这是更有实际意义的紧下界，所以多数资料会这么表述。

• 总结一下：Big Ω的定义本身是灵活的，要看你针对的输入集：

  • 如果是“存在至少一个输入”满足下界，那Ω(1)没问题；
  • 如果是“所有输入中的最坏情况的下界”，那线性搜索的紧下界就是Ω(n)，这也是算法分析中更受关注的部分，因为它反映了算法在最坏情况下的最低性能要求。

内容的提问来源于stack exchange，提问作者pfernandom