Какова временная сложность этой функции деления (не используются операторы деления или умножения)? - PullRequest
Новая
       72

Какова временная сложность этой функции деления (не используются операторы деления или умножения)?

0 голосов
/ 22 мая 2019

Я решил этот вопрос по коду https://leetcode.com/problems/divide-two-integers/. Цель состоит в том, чтобы получить частное от деления dividend на divisor без использования оператора умножения или деления. Вот мое решение: 

    def divide(dividend, divisor):     
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        sign = [1,-1][(dividend < 0) != (divisor < 0)]
        dividend, divisor = abs(dividend), abs(divisor)
        res = 0
        i = 0
        Q = divisor
        while dividend >= divisor:
            dividend = dividend - Q
            Q <<= 1
            res += (1 << i)
            i+=1
            if dividend < Q:
                Q = divisor
                i = 0

        if sign == -1:
            res = -res

        if res < -2**31 or res > 2**31 -1:
            return 2**31 - 1

        return res

Поэтому у меня возникли проблемы с анализом временной сложности этого решения. Я знаю, что это должно быть O(log(something)). Обычно для алгоритмов мы говорим, что они равны O(log(n)), когда вход делится на 2 на каждой итерации, но здесь я умножаю divisor на 2 Q<<= 1 на каждой итерации, поэтому на каждом шаге я делаю больший шаг к решению. Очевидно, что если dividend совпадает с большим divisor, мой алгоритм будет быстрее. Точно так же, чем больше dividend для того же divisor, тем медленнее время выполнения.

Я предполагаю, что уравнение, управляющее временем выполнения этого алгоритма, в основном имеет форму O (делитель / делитель) (это деление) с некоторыми журналами, чтобы учесть мое умножение Q на 2 на каждом шаге Q <<= 1 ... я не могу понять что именно.

EDIT:

Когда я впервые опубликовал вопрос, алгоритм которого я разместил ниже, ответ Алена Мериго основан на этом алгоритме. Разница между версией сверху и той, что выше, заключается в том, что мои дивиденды никогда не опускаются ниже 0, что приводит к ускорению времени выполнения. 

    def divide(dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        sign = [1,-1][(dividend < 0) != (divisor < 0)]
        dividend, divisor = abs(dividend), abs(divisor)
        res = 0
        i = 0
        tmp_divisor = divisor
        while dividend >= divisor:
            old_dividend, old_res = dividend, res
            dividend = dividend - tmp_divisor
            tmp_divisor <<= 1
            res += (1 << i)
            i+=1
            if dividend < 0:
                dividend = old_dividend
                res = old_res
                tmp_divisor >>= 2
                i -= 2

        if sign == -1:
            res = -res

        if res < -2**31 or res > 2**31 -1:
            return 2**31 - 1

        return res

Ответы [ 2 ]

1 голос
/ 23 мая 2019

Ваш алгоритм O (m ^ 2) в худшем случае, где m - количество битов в результате. С точки зрения входных данных это будет O (log (дивиденд / делитель) ^ 2).

Чтобы понять почему, подумайте о том, что делает ваш цикл. Пусть a = дивиденд, b = делитель. Цикл вычитает b, 2b, 4b, 8b, ... из a, пока он достаточно большой, затем повторяет эту последовательность снова и снова до a<b.

Его можно эквивалентно записать в виде двух вложенных циклов: 

while dividend >= divisor:
    Q = divisor
    i = 0
    while Q <= dividend:
        dividend = dividend - Q
        Q <<= 1
        res += (1 << i)
        i+=1

Для каждой итерации внешнего цикла внутренний цикл будет выполнять меньше итераций, поскольку dividend меньше. В худшем случае внутренний цикл будет выполнять только одну итерацию меньше для каждой итерации внешнего цикла. Это происходит, когда результат равен 1 + 3 + 7 + 15 + ... + (2 ^ n-1) для некоторого n. В этом случае можно показать, что n = O (log (результат)), но общее число итераций внутреннего цикла равно O (n ^ 2), то есть квадратично по размеру результата.

Чтобы сделать это линейным по размеру результата, сначала вычислите самые большие необходимые значения Q и i. Затем работайте в обратном направлении, вычитая 1 из i и сдвигая Q в каждую итерацию. Это гарантирует не более 2n итераций.

1 голос
/ 23 мая 2019

В худшем случае сложность легко найти.

Каждая итерация генерирует бит результата, а количество итераций равно количеству бит в частном.

Когда делитель= 1, частное = дивиденд, и в этом случае число итераций равно количеству битов в дивиденде после начального (наиболее значимого) 1. Оно максимизируется, когда дивиденд = 2 ^ (n-1) + k, где nчисло битов и k любое число, например 1≤k <2 ^ (n-1).Это, очевидно, будет наихудшим случаем. </p>

После первой итерации, дивиденд = делитель-дивиденд (= дивиденд-1) и делитель = 2 ^ 1

После итерации м, делитель = 2 ^ ми дивиденд = дивиденд- (1 + 2 ^ 1 + .. + 2 ^ (м-1)) = дивиденд- (2 ^ м-1)

Итерации прекращаются, когда дивиденд <0.Поскольку дивиденд = 2 ^ (n-1) + k, при k> 0 это происходит при m = n.

Следовательно, число шагов в худшем случае равно n, а сложность линейна с числомбиты дивиденда.

...