f（n）コストでのアルゴリズムの複雑さ

Question

ある関数によってコストが設定されたプロセスのアルゴリズムの複雑さを判断する必要がある場合は、O（n^2 log n） - またはどんなに大きなOが起こっても？

また、多項式の任意の項の最高次数になるのは大きなことではありませんか？私が派生物を与えるように求められたら、私は何を提供するのか分からない。

最後の質問、私は、アルゴリズムの動作回数を与える必要があり、それは本当に簡単です場合 - 大体「操作回数」の

array1, array2, array3 of size n 
for i in n: 
    array2[i] = sqrt(array1[i]) 
    array3[i] = array1[i]^2 

のように、私はちょうど私のすべての算術演算をカウントアップし、把握していました1つ（sqrtのようなもの）は複数の演算などと数えますか？それとも、それはO（n）ですか？

Answer 1

プロセスのアルゴリズムコストは、プロセスのすべてのコンポーネントのコストです。たとえば、あなたの例を使用して、我々はすべて

array1, array2, array3 of size n 

のコストを分解することができますこれは、nは各アレイの時間を要するので、O（n）の中で3N時間の合計、。

for i in n: 

つまり、ループ内のすべてにnが乗算されます。

array2[i] = sqrt(array1[i]) 

これはO（1）時間かかる。どうして？配列要素へのアクセスは一定時間です。 sqrtを取ることは一定の時間です。そして配列要素の値を設定することは一定時間です。したがって、全体の操作は一定の時間です。

array3[i] = array1[i]^2 

これは、前の操作と同じ理由でO（1）時間かかります。

したがって、実行時間はすべてO（n）時間の3n + n *（1 + 1）（厳密ではない粗い演算を使用）です。それは役に立ちますか？

実際の派生については、これに固有のテクニックがあります。ビッグ・オ表記法の正確な数学的定義を学びましたか？

This linkはbig-Oh表記の正式な定義を説明し、このようなことを証明する方法の例を示します。