サイズnのすべての入力に対してO（n）で実行されるアルゴリズムがあり、その与えられたサイズnに対してO（n^2）の事前計算ステップの後でなければならないとします。アルゴリズムはO（n）とみなされ、O（n^2）は償却されますか？あるいは、Big Oはサイズnでアルゴリズムの「実行」を1つだけ考えるので、実際の表記法O（n + n^2）またはO（n^2）を作る表記法のステップが表記法に含まれていますか？事前計算はどのように複雑な表記法で処理されますか？
明示的にコストを2つの異なる部分に分けることによってこれが説明されることは珍しくありません。例えば、range minimum query problemでは、問題のO（n ）、O（1）＆時間解決策のようなものについて人々が話すのが一般的であり、O（n ）事前計算コストとO（1）は参照コストを示します。文字列アルゴリズムの場合は、suffix tree provides an O(m)-preprocessing-time, O(n+z)-query-time solution to string searching、Aho-Corasick string matching offers an O(n)-preprocessing-time, O(m+z)-query-time solutionと表示されることがあります。
ここでのトレードオフは、実際にはユースケースに依存します。これは、前処理時間がそれに値するようになる前に、どれだけ多くのクエリを作成するかを定量的に測定することができます。
人々は通常、結果Rに得ることがステップAとB、そしてcomplexity(R) = complexity(A) + complexity(B)を実行するためにあなたを必要とする場合、彼らはなど複雑したがって
について話しているとき、物事を成し遂げるために合計時間を気に。これは、特定の例ではO(n^2)になります。
Oの分析では、最も急速に増加する用語が全体的な複雑さを支配していることに気付きました（つまり、パイプラインでは最もスループットが低いモジュールがスループットを定義します）。
しかし、それらが互いに素である場合、AおよびBの複雑さ分析は通常、分離して実行されます。
要約すると、結果が得られるまでに要する時間ですが、お互いに独立した個別のステップについての理由を（通常は）行うことができます。
O(V + E)です。
E = O(V^2)以降、BFSの複雑さを
O(E)（
E > V以降）と書くことが魅力的かもしれません。ただし、エッジがないグラフがある可能性があるので、
が正しくないになります。そのような場合でも、すべての頂点を繰り返し処理する必要があります。
多くの特定のケースでは、O（n）がO（n^3）よりもかなり遅くなる可能性があるため、O（...）表記法はアルゴリズムの動作速度を測定するものではありません。 （n^3/2ステップで実行されるものに対して10^100 nステップで実行されるアルゴリズムを想像してください）。私のアルゴリズムはO（n^2）時間で実行されると伝えれば、 n = 1000の間に長くかかります。
O（...）のポイントは、入力サイズが大きくなったときのアルゴリズムの振る舞いを指定することです。私のアルゴリズムがO（n^2）時間で実行され、n = 500で実行するのに1秒かかるとすれば、n = 1000ではなく、1.5ではなく40で4秒がかかるでしょう。
あなたの質問に答えて - いいえ、アルゴリズムはO（n）にはなりません。なぜなら、私が入力サイズを2倍にすると、時間は4で乗算されるからです。 2。
これは[Computer Science]（http://cs.stackexchange.com）の交換サイトに適した理論的な質問です。 – tadman
そこに投稿します、ありがとう。 – amoffat