大Ө表示法到底代表什么？

Question

大Ө表示法到底代表什么？

我真的很困惑大O，大欧米茄和大Theta表示法之间的区别。

我知道大O是上界，大欧米茄是下界，但是大Ө(θ)到底代表什么呢？

我读到它的意思是紧束缚但这意味着什么？

Answer 1

这意味着该算法在给定的函数中同时是大O和大Omega.例如，如果是Ө(n)，那么就会有一些常数k，这样您的函数(运行时，不管是什么)都比n*k足够大n，以及其他常量K使您的函数小于n*K足够大n.换句话说，对于足够大的n，它夹在两个线性函数之间：为k < K和n足够大，n*k < f(n) < n*K