在O(m*log m)中计算'初始列表'的算法

Question

目标是编写一个算法,计算复杂度等级中的"初始列表"(数据结构),优于O(m ^ 2)

什么是初始清单？

我们U是一个元组(例如{(2,5), (5,1), (9,0), (6,4)}).

步骤1:

L1由元组的第一个元素排序:

L1 = [ (2,5), (5,1), (6,4), (9,0) ]

和第二个L2:

L2 = [ (9,0), (5,1), (6,4), (2,5) ]

第2步:

将第二个列表中的元组e的索引添加到第一个列表中的元组e:

L1 = [ (2,5,3), (5,1,1), (6,4,2), (9,0,0) ]

和另一种方式:

L2 = [ (9,0,3), (5,1,1), (6,4,2), (2,5,0) ]

L1和L2现在被称为U的初始列表.

---

第一个实现思路当然是O(m ^ 2)中的详尽算法

U = {(2,5), (5,1), (9,0), (6,4)}

m = len(U)

#step 1:
L1 = [e for e in U]
L1.sort()
L2 = [e for e in U]
L2.sort(key=lambda tup: tup[1])

#step 2:
help = []*len(L1)
for i in range(len(L1)):
    help[i] = L1[i][0], L1[i][1], L2.index(L1[i])

for i in range(len(L2)):
    L2[i] = L2[i][0], L2[i][1], L1.index(L2[i])

L1 = help

# >>> L1
# [(2, 5, 3), (5, 1, 1), (6, 4, 2), (9, 0, 0)]
# >>> L2
# [(9, 0, 3), (5, 1, 1), (6, 4, 2), (2, 5, 0)]

这样可行.但是在for-loop(O(m))中调用索引(O(m))会使其复杂性成为二次方.但是如何在O(m*log m)中编写算法呢？

Answer 1

是的。O(m * log m) 的一种可能性是仅排序 3 次。Python 中的排序函数 List.sort() 的复杂度为 O(m * log m)：

from copy import deepcopy

U = {(2,5), (5,1), (9,0), (6,4)}
m = len(U)

h = sorted(U) #O(m * log m)
for i in range(len(h)): #O(m)
  (u,v) = h[i]
  h[i] = (u,v,i)
h.sort(key=lambda tup: tup[1]) #O(m * log m)

L1 = deepcopy(h)
L2 = h

for i in range(len(L1)): #O(m)
  (u,v,_) = L1[i]
  L1[i] = (u,v,i) #reset indices i
L1.sort() #O(m * log m)

print(L1)
print(L2)

# [(2, 5, 3), (5, 1, 1), (6, 4, 2), (9, 0, 0)]
# [(9, 0, 3), (5, 1, 1), (6, 4, 2), (2, 5, 0)]