Временная сложность рекурсивного алгоритма, который ничего не возвращает - PullRequest
Новая
       27

Временная сложность рекурсивного алгоритма, который ничего не возвращает

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

Я работаю над проектом, который имеет дело с проблемой ранца 0-1, где мне нужно изучить другой метод, чтобы решить / приблизить решение.

Первый алгоритм - это метод возврата. Мне нужно определить сложность времени этого: 

Knapsack(length, currentWeight):
    global currentSolution, optimalSolution, optimalValue
    if(length == N) then
        if(sum(i = 1 to numberItems of vi * xi) > optimalValue) then
            optimalValue = sum(i = 1 to numberItems of vi * xi)
            optimalSolution = currentSolution
        end
    else
        if(currentWeight + weights[length] <= maxWeight) then
            currentSolution[length] = 1
            Knapsack(length + 1, currentWeight + weights[length])
            currentSolution[length] = 0
            Knapsack(length + 1, currentWeight)
        else
            currentSolution[length] = 0
            Knapsack(length + 1, currentWeight)
        end
    end

Не знаю, с чего и как начать. Примером, который я видел в классе, были алгоритмы, в которых размер данных уменьшался при каждом рекурсивном вызове. Должен ли я рассматривать только наихудший случай, когда все рекурсивные вызовы выполняются из первой части (где currentWeight + weights[length] <= maxWeight верно)?

Спасибо!

...