3

このアルゴリズムの時間の複雑さと、それが 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)
4

2 に答える 2

2

再帰のため、divide（）は最大n回呼び出されます。

nビット整数の単純な算術演算にO（n）時間がかかるとします。（これは、私が知っているすべての大きな整数の実装に当てはまります。たとえば、Pythonでは、大きな整数に1を追加すると、すべてがコピーされます。）

次に、n回まで発生する有限数の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
于 2009-04-23T14:22:03.753 に答える
1

xのすべてのビットが1（たとえば、0xffff）である最悪のケースは、O（n）です。秘訣は、再帰を反復に変換することです。

于 2009-04-23T16:38:54.273 に答える