Итеративный, восходящий, разделяй и властвуй алгоритм - PullRequest
Новая
       69

Итеративный, восходящий, разделяй и властвуй алгоритм

1 голос
/ 27 апреля 2020

Я читал эту статью LeetCode о проблеме общего алгоритма, "Longest Common Prefix". Они показывают несколько разных подходов, но мой вопрос касается просто «Разделяй и властвуй». В его примере показан типичный рекурсивный подход «сверху вниз», который вы часто видите в книгах и блогах повсюду.

Глядя на это, я подумал, что я смогу сделать это «итеративно» и «снизу вверх». Что-то вроде подхода сортировки слиянием снизу вверх Итак, вот где я оказался: 

// type "Stack", function "prefix", and "min" implementations are not shown for brevity.
// Just assume they're defined somewhere and they work correctly.
//
// "prefix" function accepts two strings and returns a string
// Examples:
// prefix("abcd", "ab") returns "ab"
// prefix("abcd", "efgh") returns ""
// ... you get the idea.
//
// "min" does exactly what you'd expect. Its arguments are both type int.
func lcpDAndC(a []string) string {
        n := len(a)

        if n == 0 {
                return ""
        }

        var (
                stack Stack
                p, q  string
        )
        for lo := 0; lo < n; lo += 2 {
                hi := min(lo+1, n-1)
                stack = stack.Push(prefix(a[lo], a[hi])
        }

        for stack.Len() > 1 {
                p, q = stack.Pop2()
                stack.Push(prefix(p, q))
        }

        return stack.Pop1()
}

Итак, мой вопрос: это все еще считается «снизу вверх» и «разделяй и властвуй»? Я думаю, можно с уверенностью предположить, что начинать сразу с листьев (снизу вверх) может быть просто работа с двумя элементами одновременно, когда он проходит через массив один раз («разделяй» ... но также «побеждай»? «). Стек здесь, конечно, играет ту же роль, что и стек вызовов в рекурсивном подходе. Хотя очередь будет работать так же хорошо, что является еще одной причиной, по которой я думаю, что ушел от глубокого конца.

Если это неправильное применение «снизу вверх» и «разделяй» и победить, "это хотя бы применимо к какой-то другой теории, о которой я не знаю?

1 Ответ

0 голосов
/ 27 апреля 2020

В статье используется рекурсия Top Down, так как они разбивают большие регистры на меньшие, а затем объединяют результат меньших.

В вызовах функций рекурсии они помещаются друг на друга на стек вызовов функций. Они выталкиваются либо

(1) Once the base case is reached

или

(2) Results of function calls above them in the stack has been computed and it's their turn now.

Ваш код не выполняет Bottom Up рекурсию и также не D&C,

Рассмотрим этот случай: -

["care", "car", "cat", "cater", "click", "clang", "core", "коралл"]

Стек Изначально: - 

cor
cl
cat
car

Пока L oop Итерация # 1: 

c
cat
car

Пока L oop Итерация # 2: 

c
car

В то время как L oop Итерация # 3: 

c

Ваш while l oop комбинирует элементы последовательно и не использует свойство D&C , Если вы измените lo+=2 в for для l oop на lo+=1, тогда ваш код будет таким же, как Approach 1: Horizontal scanning.

. Однако использование очереди сделает код рекурсией Bottom-Up. Обратите внимание, что каждый раз, когда два элемента выталкиваются, они представляют две взаимоисключающие половины, которые также были бы найдены в дереве рекурсии Top Down подхода. Рассмотрим этот случай: -

["care", "car", "cat", "cater", "click", "clang", "core", "коралл"]

Изначально очередь: - 

cor
cl
cat
car

Пока L oop Итерация # 1: 

ca
cor
cl

Пока L oop Итерация # 2: 

c
ca

Пока L oop Итерация № 3: 

c
...