Сложность следующего алгоритма генерации чисел TaxiCab?

Question

Ниже приведен алгоритм генерации номеров такси с использованием очереди приоритетов (pq). Vector - это произвольный тип данных, который позволяет хранить два числа и их кубическую сумму. Для тех, кто не знает (хотя вам действительно не нужно знать), номер такси является целым числом, которое может быть выражено в виде суммы двух кубов целых чисел двумя разными способами: a^3+b^3 = c^3+d^3. Примером может быть 1729 = 12^3 + 1^3 = 10^3 + 9^3

for i = 1..n 
pq.insert(Vector(i^3+i^3,i,i)) 

prev = Vector(0, 0, 0) 

while not pq.empty() 
curr = pq.deleteMin() 
if prev[0] == curr[0] 
     print curr[0] is a Taxicab number that can be expressed as 
     prev[1]^3 + prev[2]^3 and curr[1]^3 + curr[2]^3 
prev = curr 
if curr[2] < N 
    j = curr[2] + 1 
    pq.insert(Vector(curr[1]^3 + j^3, curr[1], j)) 

Я знаю, вставив элемент в приоритетной очереди является O(log n), но я не знаю, как это связано с пространством и временной сложностью. Может кто-нибудь помочь?

Answer 1

Это определенно не хуже, чем O(N^2 log N), хотя можно было бы дать более жесткие ограничения для него.

Этот блок кода:

if curr[2] < N 
    j = curr[2] + 1 
    pq.insert(Vector(curr[1]^3 + j^3, curr[1], j)) 

делает код примерно эквивалентны, но несколько более эффективен, чем:

possibles = empty list 
for i = 1..n 
    for j in i+1..n 
     possibles.append(Vector(i^3 + j^3, i, j)) 
sort(possible_numbers) 

for i = 1..n 
    prev = possibles[i] 
    curr = possibles[i + 1] 
    if prev[0] == curr[0] 
     print curr[0] is a Taxicab number that can be expressed as 
     prev[1]^3 + prev[2]^3 and curr[1]^3 + curr[2]^3 

размер списка, O(N^2)-плюсом делает сортировку он O(N^2 log(N)). Второй цикл - O(N), который составляет код O(N^2 log N).