Существует n пакетов, пронумерованных от 1 до n. Набор K пар (i, j) определяет список зависимостей, так что пакет j не может быть установлен без установки пакета i.
Придумайте алгоритм линейного времени, который берет список K и выдает список всех пакетов, необходимых для установки пакета 1.
Вот моя попытка:
function algortihm(n,K)
radix sort K(i,j) on key j
dependencies <- arr size n //declare array
currPackage <- 1
tempArr <- K
function func(currPackage, K)
dependencies.append(currPackage)
count <- -1
for (i,j) in K:
if j not in dependencies:
count <- count + 1
if j == currPackage:
tempArr.remove(count)
func(i, tempArr)
endif
endif
if j > currPackage:
break
endif
endfor
endfunction
return dependencies
endfunction
Используя этот вход K = (1, 2) (3, 2) (3, 4) (4, 1) (5, 1) (5, 4) (6, 8) (8, 3) (7 , 6)
Radix-сортировка имеет сложность O (n) и сократит количество повторений списка, потому что если мы сортируем по зависимостям (ключ j), то мы знаем, что как только j превысит размер пакета, мы знаем, что нет больше списков зависимостей и цикл for можно разорвать.
Список после сортировки: (4, 1) (5, 1) (1, 2) (3, 2) (8, 3) (3, 4) (5, 4) (7, 6) (6, 8)
Кроме того, каждый раз, когда обнаруживается зависимость, она удаляется из временного массива, который затем рекурсивно передается в функцию.
Это также гарантирует, что вызов или итерация / сравнение не будут выполнены, если зависимость уже записана.
Это работает примерно с 37 сравнениями, но я знаю, что это не линейное время. Я просто не могу определить, что будет быстрее, чем то, к чему я уже привык, сложно проанализировать сложность предложенного мной алгоритма, но я считаю, что это O (n ^ 2 / b)