最大時間計算量を求める問題なので、この下の解説を読んでも全く意味が分からないのですが、どなたか分かり

最大時間計算量を求める問題なので、この下の解説を読んでも全く意味が分からないのですが、どなたか分かりやすく説明してくださる方いませんでしょうか？？

No.2 回答者： stega 回答日時： 2018/06/29 09:55

下記はわかった上でわからないということですか？

プログラムの説明として
各行の下にコメントを挿入しました。
ダブルスラッシュ(//)はCの構文で、コメントの前につけます。
また、この書籍では、代入命令に←を使ってますが、通常=をつかいます。
---------------------
big←bigD[1];
//bigにD[1]の内容を代入

for(i=1; i≦n; i=i+1){
//for()に続く{}内を
//繰り返す。
//()内の意味は
//　( 変数iを１で初期化;
//　 i≦nなら{}内を実行;
// 最後にiをi+1で
// 置き換えて,ここに戻る）

if(D[i]>big){
//分岐命令
//()内の条件が成立したら
//続く{}内を実行する

　　　big←D[i];
//bigにD[i]を代入。
}
//ifの終わり
}
//forの終わり

print(big)；
//bigを出力する
---------------------

No.1 回答者： k-841 回答日時： 2018/06/28 01:26

この文章で前提にしているのは、アルゴリズムの行を最小単位として、最悪何行実行されるか（繰り返しの場合は実行されるごとに1回とカウントする）ということだと思います。

最悪の場合、3行目の条件が必ず真になり、4行目が毎回実行されることになります。これを数えてみると3nになるということです。nを3とか5とかと仮定して、実際にそれぞれ何回実行されるか数えてみるとわかると思います。

ちなみに、実際のコンピュータに計算させる場合はこんなに単純ではありません。
この説明では、2行目のfor文も4行目の代入も7行目の印刷もすべて同じ計算量として取り扱っていますが、実は行によって計算量は全然違います。

2行目のfor文は、
1回目だけ
　iに2を代入する
1回目からn-1回目まで、
　iとnを比較し、大小関係を割り出す
　大小関係の結果が偽だった場合に7行目にジャンプする
2回目からn-1回目まで
　iに1を加える

また、3行目のif文は次のような処理です。
　D[i]のメモリ上の場所（番地）を計算によって求める
　D[i]の値をメモリの上記で求めた場所から読む
　読んだ値とbigを比較し、大小関係を割り出す
　大小関係の結果が偽だった場合に2行目へジャンプする

4行目は、既に3行目でD[i]の値をメモリから読んであり、値を保持している前提で、
　bigにその値を代入する
また、計算式が見えない6行目には、2行目へ無条件でジャンプする、という処理があります。

7行目のprint文は、上記の計算よりもはるかにたくさんの処理が必要です。