Какова временная сложность этого алгоритма BFS? - PullRequest
Новая
       36

Какова временная сложность этого алгоритма BFS?

0 голосов
/ 26 июня 2019

Для вопроса https://leetcode.com/problems/perfect-squares/ Я решил это, используя следующий алгоритм.Проблема в том, что 

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

В основном он пытается перейти от номера цели к 0, вычитая каждое возможное число: [1, 4, 9, .. sqrt (n)], а затем выполняетта же работа для каждого из полученных чисел.У меня проблемы с пониманием временной сложности этого алгоритма, так как ветвление на каждом уровне составляет sqrt (n) раз, но некоторые ветки обречены на раннее завершение ... 

def numSquares(n):


        squares = [i**2 for i in range(1, int(n**0.5)+1)]

        step = 1
        queue = {n}

        while queue:
            tempQueue = set()

            for node in queue:
                for square in squares:
                    if node-square == 0:
                        return step
                    if node < square:
                        break
                    tempQueue.add(node-square)

            queue = tempQueue
            step += 1

Ответы [ 2 ]

1 голос
/ 26 июня 2019

Некоторые наблюдения:

  1. Количество квадратов до n равно √n (с точностью до ближайшего целого числа)
  2. После первой итерации цикла while, tempQueue будет иметь √n записей
  3. tempQueue никогда не может содержать более n записей, поскольку все эти значения положительны, меньше n и уникальны.
  4. Каждое натуральное число можно записать в виде суммы четырех целочисленных квадратов . Это означает, что цикл while вашего алгоритма BFS будет повторяться не более 4 раз. Если оператор return не выполнялся ни на одной из первых 3 итераций, он гарантированно будет выполняться в 4 th .
  5. Каждый оператор (кроме инициализации squares) выполняется в постоянное время, даже вызов .add().
  6. Инициализация squares имеет цикл обработки списка, который имеет √n итераций, и range выполняется в постоянное время, так что инициализация имеет временную сложность O (√n ) .

Теперь мы можем установить предельное число выполнений оператора if node-square == 0 (или любого другого оператора в теле самого внутреннего цикла):

1⋅√n + √n⋅√n + n⋅√n + n⋅√n

Каждое из 4 слагаемых соответствует итерации цикла while. Левый коэффициент каждого продукта соответствует максимальному размеру queue в этой конкретной итерации, а коэффициент справа соответствует размеру squares (всегда один и тот же). Это упрощает до:

√n + n + 2n 3⁄2

С точки зрения сложности времени это:

O (n 3⁄2 )

Это наихудший вариант сложности времени. Когда цикл while должен повторяться только дважды, это O (n) , а когда только один раз (когда n - квадрат), это O ( √n) .

1 голос
/ 26 июня 2019

Если вы думаете о том, что вы делаете, вы можете себе представить, что вы выполняете поиск в ширину по графику с n + 1 узлами (все натуральные числа от 0 до n включительно) и некоторым числомребра м, которые мы определим позже.Ваш график в основном представлен в виде списка смежности, так как в каждой точке вы перебираете все исходящие ребра (квадраты меньше или равны вашему числу) и останавливаетесь, как только вы считаете слишком большой квадрат.В результате время выполнения будет O (n + m), и все, что нам теперь нужно сделать, это выяснить, что такое m.

(здесь есть еще одна стоимость в вычислении всех квадратных корней до и включаяn, но это занимает время O (n 1/2 ), в котором преобладает член O (n).)

Если подумать, то количество исходящих ребер изкаждое число k будет определяться числом совершенных квадратов, меньшим или равным k.Это значение равно ⌊√k⌋ (проверьте это на нескольких примерах - это работает!).Это означает, что общее число ребер ограничено сверху как

√0 + √1 + √2 + ... + √n

Мы можем показать, чтоэта сумма равна Θ (n 3/2 ).Во-первых, мы ограничим эту сумму сверху в O (n 3/2 ), что мы можем сделать, отметив, что

√0 + √1 + √2 +... + √n

≤ √n + √n + √ n + ... + √n (n + 1) раз

= (n +1) √n

= O (n 3/2 ).

Чтобы ограничить это в Ω (n 3/2 ), обратите внимание, что

√0 + √1 + √2 + ... + √n

≥ √ (n / 2) + √ (n / 2 +1) + ... + √ (n) * (исключить первую половину терминов)

≥ √ (n / 2) + √ (n / 2) + ... + √ (n /2)

= (n / 2) √ (n / 2)

= Ω (n 3/2 ).

Таким образом, в целом, число ребер равно Θ (n 3/2 ), поэтому, используя регулярный анализ поиска в ширину, мы можем увидеть, что время выполнения будет O (n 3/2 ).

Эта граница, вероятно, не жесткая, потому что это предполагает, что вы посещаете каждый отдельный узел и каждое ребро, чего не произойдет.Тем не менее, я не уверен, как ужесточить ситуацию намного дальше этого.

Как примечание - это было бы отличное место для использования поиска A * вместо поиска в ширину, так какВы можете довольно легко придумать эвристику, чтобы недооценить оставшееся общее расстояние (скажем, взять число и разделить его на наибольший идеальный квадрат меньше его).Это заставило бы поиск сосредоточиться на чрезвычайно многообещающих путях, которые быстро переходят к 0, а не на менее удачные пути, как, например, всегда предпринимаются шаги первого размера.

Надеюсь, это поможет!

...