連続実行時の複雑さ

Question

3つのアルゴリズム（A1、A2、A3）があり、推定時刻複雑度はそれぞれO(n Log n),O(K n)、O(Q n)です。ここで、KとQはアクションの異なるパラメータです。次に、これらの3つのアルゴリズムを連続して実行する第4のアルゴリズムがあります（それぞれが前の結果を必要とします）。

アルゴリズムスイートの複雑さの合計をどのように見積もるべきか、私は混乱しています。私が理解できる限り、O(n Log n)はO(K n)とO(Q n)より速く成長するため、時間消費の点で最も重要な部分はA1で、おそらくnの場合には最も関連性の高い動作になります。しかし、それはA1が完了した後でさえ、まだA2とA3が多くの時間を取ることを反映しません。

私はそれをどのように考慮すべきなのでしょうか？複雑さがO(n Log n)であると言うだけで十分ですか？

Answer 1

合計時間の複雑さがある：KとQはそのパラメータであると仮定した場合

O（NログN）+ O（K n）が+ O（Q n）が

Log nよりも遅いまたは同様に成長し、次いで、総時間の複雑性は、次のとおり

O（NログN）

私たちはbig-o表記を使用しているためです。それ以外の場合、合計時間複雑度は初期合計（またはその一部）です。

---

アイデアはnが成長したときにに他の用語を支配する用語を維持することです。