Какова временная сложность этого агорифма (который решает вопрос 650 по leetcode) (вопрос 2)?

Question

Здравствуйте, я работал над https://leetcode.com/problems/2-keys-keyboard/ и натолкнулся на этот вопрос динамического программирования.

Вы начинаете с 'A' на пустой странице, и вы получите число n, когда вы закончите, у вас должно быть n раз 'A' на странице. Подвох в том, что вам разрешено копировать только 2 операции (и вы можете копировать только общее количество A, находящихся в данный момент на странице) и вставлять -> найти минимальное количество операций, чтобы получить n 'A' на странице.

Я решил эту проблему, но затем нашел лучшее решение в разделе обсуждения leetcode -> и я не могу понять, как сложность по времени.

    def minSteps(self, n):
        factors = 0
        i=2
        while i <= n:
            while n % i == 0:
                factors += i
                n /= i
            i+=1
        return factors

То, как это работает, i никогда не будет больше, чем самый большой простой коэффициент p из n, поэтому внешний цикл равен O(p), а внутренний цикл while в основном O(logn), так как мы делим n /= i на каждой итерации.

Но, как я смотрю на это, мы делаем O(logn) делений для внутреннего цикла, в то время как внешний цикл равен O(p), поэтому, используя агрегатный анализ, эта функция в основном O(max(p, logn)) это правильно?

Любая помощь приветствуется.

Answer 1

Ваши рассуждения верны: O (max (p, logn)) дает сложность времени, предполагая, что арифметические операции занимают постоянное время.Это предположение неверно для произвольно больших n , которые не помещались бы в хранилище чисел с фиксированным размером машины, и где вам понадобились бы операции Big-Integer, которые имеют непостоянное времясложность.Но я буду игнорировать это.

Все еще странно выражать сложность в терминах p , когда это не входные данные (а производные от них).Вы вводите только n , поэтому имеет смысл выразить сложность в виде только n .

Худший случай

Понятно, когда n простое, алгоритм O (n) - внутренний цикл никогда не повторяется.

Для простого n алгоритм будетзаймет больше времени, чем для n + 1 , так как даже наименьший коэффициент n + 1 (т.е. 2) уменьшит вдвое количество итераций внешнего цикла и все же только добавит1 блок постоянной работы во внутреннем цикле.

Итак, O (n) - наихудший случай.

Средний случай

Для среднего случая отметим деление n происходит столько раз, сколько n имеет простые множители (считая дубликаты).Например, для n = 12 у нас есть 3 деления: n = 2 · 2 · 3

Среднее число простых факторов для 1 приближается loglogn + B , где B - некоторая константа.Таким образом, мы можем сказать, что средняя сложность времени для полного выполнения внутреннего цикла составляет O (loglogn) .

. Нам нужно добавить к этому выполнениевнешняя петля.Это соответствует среднему наибольшему простому коэффициенту.Для 1 это среднее значение приближается к Cn / logn , и поэтому имеем:

O (n / logn+ loglogn)

Теперь n / logn является здесь более важным термином, поэтому он упрощается до:

O (n / logn)