問題タブ [code-complexity]

Scalapackルーチンが実行する操作の数、特に送信するメッセージの数と単語の数をカウントする論文またはワーキングノートを誰かが知っているかどうか疑問に思っていました.

操作カウントに関しては、Golub と Van Loan の優れた Matrix Computations を参照するか、Lapack の LAWN 41 をチェックして、ScaLapack であまり変化しないと仮定することができますが、メッセージと単語のカウントについては何も見つけることができず、これは最終手段です。コードを調べます。

問題を解決しただけですが、その解決策を持っていないので、私の解決策が正しいかどうかを確認できるかどうかお願いします

BIGTHETA でコードのその部分の複雑さを見つけなければなりません。

だから、私は3番目のサイクルがそのように成長することを分析します

k -> linear until = h (h は 2^w のように大きくなる) - したがって、複雑さは log n です。

2番目については、最初のサイクルの制限は0なので、複雑さはlog nだと思います。

最初の 2^N = 2^N-1 について、複雑さは n

合計の複雑さは n * log n です

このコードは、並べ替えられていない配列を受け取り、挿入並べ替えを使用して並べ替えます。重複が並べ替えられていない配列で一緒に配置されると、複数のシフトの複雑さが原因で、重複が一緒に配置された場合に複数回移動するアイテムがないことを確認して作成O(N^2)しようとしました。O(N)

しかし、重複が一緒に配置されていない場合、複雑さが残りO(N^2)ます。O(N)この場合も複雑にできますか？

このコードは、指定されたリスト内の指定された要素の位置を見つけるためのものです。

その複雑さを知るために、私は関数とリストfilterを取ることを考えました。g[0..length-1]

今、私はの複雑さが何であるか、または機能のためにループが発生positions2するかどうかを理解できません。(n)filter

これよりも複雑さを軽減するために、よりコンパクトなコードを記述する他の方法があるかどうかを提案してください。

現在、Python 関数の「基本的なステップ」を見つけようとしています。O(1)基本的なステップは、それ自体が複雑なコード内のポイントです。私はこの関数でそれを見つけるのに苦労しています:

total += numbers[i]*numbers[j]関数内の他のどのステートメントよりも多く実行する必要があるため、ここでの基本的なステップは事実だと思いたいのですが、それを理解する能力に完全には確信が持てません。どんな助けでも大歓迎です！