Является ли сложность моего кода во время выполнения O (a b)?

#python

Вопрос:

Я только что решил эту проблему в LeetCode. Это довольно просто, но я не уверен в сложности кода во время выполнения. кто-нибудь может мне это объяснить.

 def addBinary(self, a: str, b: str) -> str:
        carry = 0
        result = ''

        a = list(a)
        b = list(b)

        while a or b or carry:
            if a:
                carry  = int(a.pop())
            if b:
                carry  = int(b.pop())

            result  = str(carry %2)
            carry //= 2

        return result[::-1]

Ответ №1:

Ваш цикл будет выполняться до тех пор, пока в a или в b ничего не останется, а перенос равен 0. Каждый раз, когда вы выполняете итерацию, вы уменьшаете количество записей в a и b на единицу. Следовательно, общее количество итераций, max(len(a),len(b)) x где x , равно 1, если в конце что-то осталось в переносе, и 0 в противном случае, поскольку x в основном ограничено константой (константа 1), вы можете игнорировать это для асимптотической части.

Обратите внимание, что (len(a) len(b))/2<=max(len(a),len(b))<=len(a) len(b) так

max(len(a),len(b)) 1 равно O(len(a) len (b))

и len(a) len(b) равно O( max(len(a),len(b)))

1. Я получил отрицательный результат. Я знаю, просто хочу знать, плох ли мой вопрос? как будто контент плохой или так, как я спрашиваю?

2. Я не уверен, но я предполагаю, что у него есть вкус «домашней работы». Это может помочь, если вы добавите контекст, например, объясните, с какой частью вычисления сложности вы боролись.

3. Ох. Я только начал использовать stackoverflow, я не очень много знаю об этом. но я просто хочу знать, что временная сложность ничего не говорит о домашней работе. как я уже сказал, я решил это на leetcode. но я просто не знал большого O

Ответ №2:

Нет, это O(max(len(a), len(b)) . Каждая итерация while цикла обрабатывает один элемент a и b . Даже когда он достиг конца более короткой строки, он должен выполнять if тест для этой строки каждый раз, когда он обрабатывает элемент более длинной строки. И последние два оператора в цикле выполняются в любом случае.

В целях вычисления сложности мы игнорируем тот факт, что он выполняет на одну инструкцию меньше на каждой итерации, когда достигает конца более короткой строки.

Ответ №3:

Здесь наихудшая временная сложность может быть O(max(len(a),len(b)))

Объяснение:

Пусть a = ‘11111111’ и b = ’11’

Цикл while будет повторяться до тех пор, пока оба списка a и список b не станут пустыми и перенос будет равен 0, в нашем примере b будет пустым после 2-й итерации, но все же цикл while будет продолжаться до тех пор, пока список a не станет пустым, для len (max (a, b)) раз, т.Е. len (a) = 8 итераций, и даже после этого он будет повторяться еще раз, чтобы добавить перенос (хотя мог быть выведен из цикла)

Решение может быть импровизированным. Подсказка: измените условие while на цикл для min(len(a),len(b))). Я оставлю это вам для дальнейшей реализации