big-o - 単純な乗算が n^2 時間なのはなぜですか?

Question

加算/減算などの操作は線形時間であり、「小学校」の長い乗算は n^2 時間であると読みました。なぜこれが真実なのですか？

floor(log n)nが小さいオペランドの場合、加算回数ではありませんか？同じ議論が引き算や掛け算にも当てはまります。整数を加算する代わりに長い掛け算を行うプログラムを作成するfloor(log a) * floor(log b)と、a と b がオペランドである場所が複雑になるのではないでしょうか?

Answer 1

答えは、「n」が何であるかによって異なります。加算が O(n) で、乗算 (単純なアルゴリズムを使用) が O(n^2) であると彼らが言うとき、n はビットまたはその他の単位の数値の長さです。この定義が使用されるのは、任意精度の算術演算が「数字」のリスト (必ずしも基数 10 ではない) に対する演算として実装されているためです。

n が加算または乗算される数値である場合、数値が log n 空間に格納されている限り、複雑さは log n であり、正の n の場合は (log n)^2 になります。

Answer 2

(たとえば) の乗算に対する単純なアプローチは、次のように273 x 12(分配規則を使用して) 展開され(200 + 70 + 3) x (10 + 2)ます。

  200 x 10 + 200 x  2 
+  70 x 10 +  70 x  2
+   3 x 10 +   3 x  2

この単純化のアイデアは、乗算を簡単に実行できるものに減らすことです。小学校の数学では、0 から 9 までの九九を知っていると仮定すると、数字を扱うことになります。各「数字」が 0 から 9999 までの値である (10 進数の印刷を容易にするため) bignum ライブラリの場合、同じ規則が適用され、10,000 未満の数値を比較的頻繁に乗算できます)。

したがって、が桁数である場合、 「定数」操作の数は「桁」カウントの積とともに増加する傾向があるためn、複雑さは確かにです。O(n2)

これは、数字の定義がわずかに異なる場合でも当てはまります (0 から 9999 までの値であったり、2 進数0またはのいずれかであるなど1)。