私はまずO(n*log(n))時に何かを行い、次にO(n^2)時に何か他のことをするアルゴリズムを持っています。私はlog(n) + nが+ nによって支配されているため、合計複雑さがO（n * log n）の仕事をし、O（n^2）の仕事をするコードの複雑さは何ですか？
O(n*log(n) + n^2)
= O(n*(log(n) + n))
= O(n^2)
になることを修正するのですか？
O(n log n)はO(n^2)のサブセットです。しかし、正式な証明は適切な定数を選択して構成することから成り立つ。
両方のコールの確率が等しい場合、あなたは正しいです。しかし、両者の確率が等しくない場合、貴重な高価なコール（n²）を多数の高速コール（n log（n））に分割する償却分析を行う必要があります。
たとえば、クイックソート（一般にn log（n）がかかりますが、rarlyはn²です）では、償却分析のために平均実行時間がn log（n）であることを証明できます。
私はあなたがその質問を誤解したと思います。私はそれを、O（n log n）時間で実行され、その後にO（n 2）時間で実行される1つのステップという2つのステップからなるアルゴリズムについて取る。確率は関係ありません。 – ruakh
次に、コーダーの回答が最適です – gartenkralle
複雑さの分析のルールの1つは、指数または低い係数が低い用語を削除する必要があることです。
nlogn vs n^2 (divide both by n)
logn vs n
LOGNは複雑で、nは、nlognの値は本当に大きいですO（nlogn + N^2）が、ある場合は、
ので、複雑方程式から削除することができますよりも、nよりも小さいですn^2と比較すると有意ではないので、これを削除してO（n^2）として書き直します。
これは間違いなく、n2項が支配的です。 –