大 Ө 符号究竟代表什么? [英] What exactly does big Ө notation represent?

问题描述

我对大 O、大 Omega 和大 Theta 符号之间的差异感到非常困惑.

I'm really confused about the differences between big O, big Omega, and big Theta notation.

我知道大 O 是上限，大 Omega 是下限，但是大 Ө (theta) 到底代表什么?

I understand that big O is the upper bound and big Omega is the lower bound, but what exactly does big Ө (theta) represent?

我读过它的意思是tight bound，但这是什么意思?

I have read that it means tight bound, but what does that mean?

推荐答案

表示给定函数中的算法既是 big-O 又是 big-Omega.

It means that the algorithm is both big-O and big-Omega in the given function.

例如，如果它是 Ө(n)，那么有一些常数 k，这样你的函数(运行时，无论如何)，大于n*k 足够大的 n 和一些其他常数 K 使得你的函数小于 n*K> 对于足够大的 n.

For example, if it is Ө(n), then there is some constant k, such that your function (run-time, whatever), is larger than n*k for sufficiently large n, and some other constant K such that your function is smaller than n*K for sufficiently large n.

换句话说，对于足够大的n，它夹在两个线性函数之间:

In other words, for sufficiently large n, it is sandwiched between two linear functions :

对于 k 和 n 足够大，n*k

For k < K and n sufficiently large, n*k < f(n) < n*K

这篇关于大 Ө 符号究竟代表什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！