7

私はこれを複数の情報源（オンラインおよび書籍）で見つけました-正方行列乗算の実行時間は、サイズnXnの行列に対してO（n ^ 3）です。（例-行列乗算アルゴリズムの時間計算量）

このステートメントは、この乗算プロセスの実行時間の上限がCn ^ 3（Cは定数）であり、n> n0（n0はこの上限が当てはまる入力）であることを示します。（http://en.wikipedia.org/wiki/Big_O_notationandΘ（n ）とO（n）の違いは何ですか？）問題は、定数Cとn0の値を導き出せないように見えることです。

私の質問-

  1. 誰かが「正方行列の乗算の大きなオーはO（n ^ 3）」というステートメントの数学的証明を提供できますか？

  2. Cとn0の値は何ですか？

4

1 に答える 1

8

  1. それぞれ0からn-1（または1からn）までの3つのforループがあります（完全に正しくない場合でも、提供したリンクに示されているように）。これにより、O（n 3）になります。それを適切な証拠に形式化することは十分に簡単なはずです。

  2. a）正式な証明の場合、実行時間は、一般に任意の算術演算と見なされる一連の演算の観点から定義する必要があります。3つのforループの内部には、2つの算術演算（1つの乗算、1つの加算）があり、したがって、C=2になります。2.n3

    b）これはn = 1から当てはまるため、n0 =0

big-Oは単なる上限であるため、このアルゴリズムの複雑さは、任意のk> = 3に対してO（n k）であると言うこともできます（big-Theta表記を使用する場合は同じではありません）。また、Cとn0をそれぞれ2と0より大きい任意の値にすることもできます（可能な限り最小の値を見つけることが要件ではないため）。

于 2012-11-22T08:22:30.607 に答える