55397


ドット演算子とアロー演算子を用いて、ベクトルのノルムを求めるアルゴリズムについて

[前の質問](https://ja.stackoverflow.com/questions/55338/%E3%83%89%E3%83%83%E3%83%88%E6%BC%94%E7%AE%97%E5%AD%90%E3%81%A8%E3%82%A2%E3%83%AD%E3%83%BC%E6%BC%94%E7%AE%97%E5%AD%90%E3%81%AE%E9%81%95%E3%81%84%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6/55342?noredirect=1#comment59365_55342)で、ドット演算子とアロー演算子の違いについて質問させていただきましたが、それぞれの演算子によってプログラムの計算量はオーダ記法では違いはあるのでしょうか。

オーダー記法で計算量を考えると、n次元のベクトルが全て0以外だった時にn回、normが計算されるのでおしなべるとO(n)という理解で合っていますか。
ドット演算子・アロー演算子のアルゴリズム共に同じO(n)でしょうか。

[前の質問より引用](https://ja.stackoverflow.com/questions/55338/%E3%83%89%E3%83%83%E3%83%88%E6%BC%94%E7%AE%97%E5%AD%90%E3%81%A8%E3%82%A2%E3%83%AD%E3%83%BC%E6%BC%94%E7%AE%97%E5%AD%90%E3%81%AE%E9%81%95%E3%81%84%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6/55342?noredirect=1#comment59365_55342)  
ドット演算子の擬似コード

[code]

    while next_address != NULL do
        norm <- norm + (*next_address).value * (*next_address).value
        next_address <- (*next_address).next
    
[/code]

アロー演算子の擬似コード

[code]

    while next_address != NULL do
        norm <- norm + next_address->value * next_address->value
        next_address <- next_address->next
    
[/code]


CC BY-SA 4.0
2019-05-29T13:15:09.447
55351
2019-05-31T05:44:22.703
2019-05-31T03:53:21.817
question
c アルゴリズム 計算量
ドット演算子とアロー演算子を用いてベクトルのノルムを求めるアルゴリズムの計算量について


正直言って、「何かBig-O記法をとんでもなく難しいものと勘違いしているんじゃないのか?」と思ってしまいます。

今回の場合、どちらの擬似コードかによらず(別にコメントに合わせて書き換える必要性は全くなかったように思いますが)ループの実行回数はベクトルの次元数`n`に対して`n`回だと言う事はわかっているはずです。

編集前を含むどの擬似コードでもループ内で実行される処理はプリミティブなもので、ベクトルの次元数に応じて計算量が変化するような処理は含まれていません。

従って結論は、

全部`O(n)`です。

* * *

ちなみにBig-
O記法は定数係数を無視したものなので、それだけでは2つのアルゴリズムの「どちらがより高速に処理できるか」と言うことを表す事はできませんので、ご注意を。

(現在表示のコードは全く等価なので、そもそも区別する意味自体がありませんが。)


CC BY-SA 4.0
2019-05-31T04:21:01.223
55388
2019-05-31T04:21:01.223
13972
55351
answer


コメント等から察するに、計算量オーダーの見積もり方を定義から確認するのが早道かな、と思いました。O(N)
な気がするのに確信が無いとのことですので、確信を持つために時間計算量が O(N) であることを証明してみます。

まずドット演算子を使った方のアルゴリズムについて考えてみます。

[code]

    while next_address != NULL do
        norm <- norm + (*next_address).value * (*next_address).value
        next_address <- (*next_address).next
    
[/code]

このアルゴリズムの最悪時間計算量を考えます。ここで、変数への代入、ポインタの dereference、構造体メンバーの参照、比較、加算、乗算にすべて等しく
1 の計算時間がかかると仮定します。変数の参照に時間はかからないとします。入力されるベクトルを V、V の長さを N として、このアルゴリズムの実行時間を
T(V, N) と書くことにします。

ベクトルの全要素がゼロでないときにループが最大回数 (N 回) まわり、1 回のループで比較も含めて時間が 11 だけかかり、最後に 1 回だけ `NULL
!= NULL` という比較をするので、以下の不等式が成り立ちます。

T(V, N) ≦ 11N + 1

したがって big-O 記法の定義から、T(V, N) = O(N) です。

アロー演算子を使った場合も、それにかかる計算時間を仮定して、計算時間を見積もることになります。アローの演算は何かしら定数時間と仮定するのが自然でしょうからそうすると、その元で上と同じように計算して、やはり最悪時間計算量は
O(N) と見積もれます（敢えて省略しています; ご自身で実際に計算してみてください！）。

補足として、最悪時間計算量ではなく平均時間計算量を求めたい場合、V がしたがう確率分布を適当に仮定して、その元で計算時間の期待値を考えることになります。


CC BY-SA 4.0
2019-05-31T05:19:34.320
55397
2019-05-31T05:44:22.703
2019-05-31T05:44:22.703
19110
19110
55351
answer