私は2つの数の加算の時間計算量が何であるかを見ようとしています。ここでは足し算はn平方と書いてあります。アルゴノート
ページ番号4の2番目の段落。
ここで、99 + 99を取ると、2つの加算演算と2つのキャリー演算を実行し、前の結果から新しい結果にキャリーを追加して、すべてを結合します。
これがn平方だとどうして言えるのかわかりません。
そのため、数値を2進数で表すと、01100011が8ビットになり、8つの加算と4つのキャリーの加算が発生する可能性があると思います。これはnの正方形のように見えますが、よくわかりません。
これを見る別の方法はありますか？n平方はどうですか？各桁でループを実行し、位置の場所、つまり10 * sum + 100 * sumなどを追加できますが、これは1つのforループで非常にうまく実行できます。