O(1)和Θ(1)有什么区别? [英] What is the difference between O(1) and Θ(1)?

问题描述

我知道它们的定义，但是为什么我有时会在教科书中看到O(1)有时是Θ(1)的原因?

I know the definitions of both of them, but what is the reason sometimes I see O(1) and other times Θ(1) written in textbooks?

谢谢.

推荐答案

Big-O符号表示一个渐近的上限，而Big-Theta符号另外表示一个渐近的下限.通常，上限是人们感兴趣的内容，因此即使Theta(something)也成立，他们也会写O(something).例如，如果您想计算未排序列表中等于x的事物数，您可能会说它可以在线性时间内完成，并且为O(n)，因为对您而言重要的是它将不会花费的时间不会超过此.但是，也确实是Omega(n)，因此是Theta(n)，因为您必须检查列表中的所有元素-不能在亚线性时间内完成.

Big-O notation expresses an asymptotic upper bound, whereas Big-Theta notation additionally expresses a asymptotic lower bound. Often, the upper bound is what people are interested in, so they write O(something), even when Theta(something) would also be true. For example, if you wanted to count the number of things that are equal to x in an unsorted list, you might say that it can be done in linear time and is O(n), because what matters to you is that it won't take any longer than that. However, it would also be true that it's Omega(n) and therefore Theta(n), since you have to examine all of the elements in the list - it can't be done in sub-linear time.

这篇关于O(1)和Θ(1)有什么区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！