下界和紧密界有什么区别? [英] What is the difference between lower bound and tight bound?

问题描述

参考此答案，什么是Theta(紧束缚)?

With the reference of this answer, what is Theta (tight bound)?

Omega是下限，很容易理解，算法可能花费的最短时间.我们知道Big-O是上限，这意味着算法可能花费的最长时间.但是我对Theta一无所知.

Omega is lower bound, quite understood, the minimum time an algorithm may take. And we know Big-O is for upper bound, means the maximum time an algorithm may take. But I have no idea regarding the Theta.

推荐答案

大O 是上限，而 Omega 是下限. Theta 同时需要Big O和Omega，所以这就是为什么它被称为 tight bound (必须同时是上限和下限)的原因.

Big O is the upper bound, while Omega is the lower bound. Theta requires both Big O and Omega, so that's why it's referred to as a tight bound (it must be both the upper and lower bound).

例如，采用Omega(n log n)的算法至少花费n log n时间，但没有上限.采用Theta(n log n)的算法是优先考虑的，因为它至少需要 n log n(Omega n log n)并且不超过 n log n(Big O n log n ).

For example, an algorithm taking Omega(n log n) takes at least n log n time, but has no upper limit. An algorithm taking Theta(n log n) is far preferential since it takes at least n log n (Omega n log n) and no more than n log n (Big O n log n).

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