質問: ドット演算子とアロー演算子を用いて、ベクトルのノルムを求めるアルゴリズムについて 前の質問で、ドット演算子とアロー演算子の違いについて質問させていただきましたが、それぞれの演算子によってプログラムの計算量はオーダ記法では違いはあるのでしょうか。 オーダー記法で計算量を考えると、n次元のベクトルが全て0以外だった時にn回、normが計算されるのでおしなべるとO(n)という理解で合っていますか。 ドット演算子・アロー演算子のアルゴリズム共に同じO(n)でしょうか。 前の質問より引用 ドット演算子の擬似コード ``` while next_address != NULL do norm <- norm + (*next_address).value * (*next_address).value next_address <- (*next_address).next ``` アロー演算子の擬似コード ``` while next_address != NULL do norm <- norm + next_address->value * next_address->value next_address <- next_address->next ```
回答: 正直言って、「何かBig-O記法をとんでもなく難しいものと勘違いしているんじゃないのか?」と思ってしまいます。 今回の場合、どちらの擬似コードかによらず(別にコメントに合わせて書き換える必要性は全くなかったように思いますが)ループの実行回数はベクトルの次元数`n`に対して`n`回だと言う事はわかっているはずです。 編集前を含むどの擬似コードでもループ内で実行される処理はプリミティブなもので、ベクトルの次元数に応じて計算量が変化するような処理は含まれていません。 従って結論は、 全部`O(n)`です。 ちなみにBig-O記法は定数係数を無視したものなので、それだけでは2つのアルゴリズムの「どちらがより高速に処理できるか」と言うことを表す事はできませんので、ご注意を。 (現在表示のコードは全く等価なので、そもそも区別する意味自体がありませんが。)