Skip to main content
 首页 » 编程设计

python之O(nlogn) 运行时方法

2024年10月25日18lyj

该函数使用 int 列表并按递增顺序生成列表中的唯一元素。例如:

    singles([4,1,4,17,1]) => [1,4,17] 

我只能在O(n^2)的运行时间内完成,想知道如何在不循环的情况下变成O(n)的运行时间。

      def singles(lst): 
        if lst==[]: return [] 
        else: 
        rest_fn = list (filter (lambda x: x!=lst[0], lst[1:])) 
        return [lst[0]] + singles(rest_fn) 

请您参考如下方法:

如上所述,根据 https://wiki.python.org/moin/TimeComplexity (引用自 Time complexity of python set operations?,它还链接到更详细的操作列表,sorted 的时间复杂度应该为 O(nlogn)。Set 的时间复杂度应该为 O(n)。因此,执行 sorted(set(input )) 应该有时间复杂度 O(n) + O(nlogn) = O(nlogn)

编辑: 如果你不能使用集合,你应该提到这一点,但作为一个提示,假设你可以使用排序,如果你使用双端队列(最差为 O(1)案例插入)。有点像

rez = deque() 
last = None 
for val in sorted(input): 
   if val != last: 
      rez.add(val) # or whatever deque uses to add to the end of the list 
      last = val