2

如何决定表达算法的时间复杂度？

O(n)我们应该选择用或来表达时间复杂度theta(n)吗？因为函数f(n)可以表示为Big-Oh(g(n))或theta (g(n))。

我们什么时候选择 big-oh 而不是 theta ？

4

1 回答 1

5

如果您还想指定下限，请使用 Big Theta 表示法。f(n) = O(g(n))说 that 以f为界g，而f(n) = Theta(g(n))说 thatf以 上下为界g。

换句话说，有常数k1和k2这样的k1 * |g(n)| <= |f(n)| <= k2 * |g(n)|

于 2011-03-19T23:46:37.030 回答