Big O表記法と述語ロジックの結合

Question

TrueまたはFalse？ ∀f[f =Ω（n^2）∧f= O（n^3）⇒f=Θ（n^2）∨f =Θ（n^3）]

Answer 1

いいえ、この文は、最良のケースはTheta（n^2）であり、最悪の場合はTheta（n^3）です。そのステートメントが真であれば、それは平均的なケースが最善のケースまたは最悪のケースと決して異なることはあり得ないことを意味し、これは真ではない。

たとえば、最良のケースがオメガ（1）であり、平均ケースがO（log n）であり、最悪ケースがO（n）であるBSTを参照してください。 （一部の人々は私に同意せず、O（log n）を最良のケースとして挙げるが、これには同意しない）。

このケースでは、Theta（n^2 log n）となる可能性があるため、平均ケースはTheta（n^2）またはTheta（n^3）のいずれかである必要はありません。 n^2）とシータ（n^3）より小さい。私は実際にがであるアルゴリズムを考えることはできませんが、あなたは少なくともそれが実際にはアルゴリズムであるとは想像できます。