time - 時間計算量の説明と追加

Question

O（logN）で何かを持っていて、それをO（1）で何かに追加した場合、全体的な複雑さはまだlogNですか？

ありがとう

Answer 1

多くの場合、big-O表記は近似値です。たとえばlogN、実際の複雑さはいつであるかを言うことができます4logN + 7。logN主な要因は変化としての振る舞いであるため、これはまだ時間であると考えられていNます。

あるアルゴリズムがある場合N^2 + logN、最も重要な用語はN^2であり、増加するにつれてlogNすぐに重要ではなくNなります...その場合、それはO(N^2)アルゴリズムの特徴的な時間計算量を表すためであると単純に言うことができます。

だからそれはあなたのニーズに依存します。単にアルゴリズムの性質を説明する必要がある場合は、logNそれで十分です。そのすべての部分を完全に分類する必要がある場合、または類似しているが最適化されたアルゴリズムと比較する必要がある場合は、すべての用語を追加してください。