このアルゴリズムの時間の複雑さと、それがなぜO（n^2）なのかを助けてくれる人は誰でも助けてください。ステップバイステップの説明は役に立ちます、ありがとう！分割アルゴリズム - 時間の複雑度
function divide(x,y)
Input: Two n-bit integers x and y, where y >= 1
Output: The quotient and remainder of x divided by y
if x = 0:
return (q,r) = (0,0)
(q,r) = divide(x/2, y)
q = 2q
r = 2r
if x is odd:
r = r + 1
if r >= y:
r = r - y
q = q + 1
return (q,r)
再帰によってdivide（）がn回呼び出されます。
単純なnビット整数の計算では、O（n）時間かかるとします。 （これは、私が知っているすべての大規模整数の実装に当てはまります。たとえば、大きな整数に1を加えると、すべてがコピーされます）。
次に、有限個のO n回までこれはO（n^n）時間かかる。
def divide(x, y):
assert y >= 1
if x == 0:
return 0, 0
q, r = divide(x // 2, y)
q *= 2
r *= 2
if x & 1:
r += 1
if r >= y:
r -= y
q += 1
return q, r
あなたはあなたのnが混乱していると思います。 1つのnビット整数に対する演算は、O（n）ではなくO（1）になります。なぜなら、nは、関数に渡されるxの値であると考えているからです。 divide（）はn回まで呼び出されません。 1024を渡すと、除算は10回だけ呼び出されます。 – paxdiablo
しかし、Pax、あなたの投稿は、xとyが「2つのnビット整数」であると言っています。 –
O（N）のNは、xの値またはビット数nのいずれかです。両方の値にすることはできません。私はbigOを2つの入力変数に依存させる一般的な配列（int []）ではなく、単一の整数単位（int）であると述べました。質問者からの明確化が必要です。 – paxdiablo
コードに "code formating"を追加できますか？今は読むのがむずかしいです。 – Skurmedel
説明が必要 - 算術演算は、基本データ型（intなど）またはそれらの配列（BigInt int配列など）で動作していますか？ – paxdiablo
いいえ、その過去の試験問題と私は今後の試験のために改訂しています。私はここに解決策を持っているが、私はそれを理解していない： 私たちは1ビットを失うアルゴリズムの各呼び出しで。だから、 n + 1コールがあります。各呼び出しは、最大で2回の乗算（左シフト）、2つの加算を1で行い、yを減算することはすべてO（n）である。したがって、合計は です。複雑さはO（n2） – KP65