big-o - 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

「操作カウント」については、すべての算術演算を数え上げて、どの演算 (sqrt など) が複数の演算としてカウントされるかを把握するだけですか?

score 0 · Accepted Answer

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

array1, array2, array3 of size n

これには配列ごとに n 時間かかるため、合計 3n 時間、つまり O(n) になります。

for i in n:

これは、ループ内のすべてが n で乗算されることを意味します。

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

これには O(1) 時間かかります。なんで？配列要素へのアクセスは一定時間です。平方根を取るのは一定時間です。また、配列要素の値の設定は一定時間です。したがって、操作全体は一定時間です。

array3[i] = array1[i] ^ 2

前の操作と同じ理由で、これには O(1) 時間がかかります。

したがって、全体の実行時間は 3n + n * ( 1 + 1) (ここでは正確ではなく大まかな計算を使用) であり、これはちょうど O(n) 時間です。それは役に立ちますか？

実際の導出に関しては、これには特定の手法があります。big-Oh表記の正確な数学的定義を学びましたか?

このリンクは、big-Oh表記の正式な定義を説明し、このことを証明する方法の例を提供します.

1 に答える 1