1

如果我有 O(logN) 的东西并将其添加到 O(1) 的东西中,整体复杂性仍然是 logN 吗?

谢谢

4

1 回答 1

1

通常大 O 表示法是一个近似值。例如,您可能会说logN实际复杂度为4logN + 7. 这仍然被认为是logN时间,因为主要因素是N变化的行为。

如果你有一些算法是N^2 + logN,那么最重要的项是N^2并且logN随着增加而迅速变得不重要N......在这种情况下,你可以简单地说它是O(N^2)因为它描述了算法的特征时间复杂度。

所以这取决于你的需求。如果您只需要描述算法的性质,那么logN就足够了。如果您需要对其中的每个部分进行完全分类或与相似但优化的算法进行比较,则添加所有术语。

于 2013-02-12T00:45:29.123 回答