時間複雜性增加說明

Question

如果我有O（logN）的東西並將其添加到O（1） 的東西是否總體複雜性仍然logN？

謝謝

Answer 1

通常大O符號是近似值。例如，當實際複雜度爲4logN + 7時，您可能會說logN。這仍然被認爲是logN時間，因爲主要因素是N的變化。

如果你有一些算法是N^2 + logN，那麼最顯著項N^2和logN很快變得不重要爲N增加......在這種情況下，你可以簡單地說，這是O(N^2)，因爲它描述的特徵時間複雜度的算法。

所以這取決於你的需求。如果您只需要描述算法的性質，那麼logN就足夠了。如果您需要對其每個部分進行完全分類或與類似但優化的算法進行比較，請添加所有術語。