这是用于计算数组O（n）复数中的倒数的算法吗？

我在Python中遇到了问题Count inversions in the array的解决方案，它使用“非比较排序算法来计算”。它对执行按位操作的代码进行2次递归调用。这是用于计算数组O（n）复数中的倒数的算法吗？

def inv_count(a, m=(1 << 32)): 
    if not m or not a: 
     return 0 
    count = 0 
    ones, zeros = [], [] 
    for n in a: 
     if n & m: 
      ones.append(n & ~m) 
     else: 
      count += len(ones) 
      zeros.append(n & ~m) 
    m /= 2 
    return count + inv_count(ones, m) + inv_count(zeros, m) 


print inv_count([1, 2, 3, 4, 5]) 
print inv_count([2, 4, 1, 3, 5]) 
print inv_count([5, 4, 3, 2, 1])

此解决方案是否真正线性O(n)？

相似，所以问题声称这是不可能的（Is there an algorithm to count array inversions in linear time?），虽然有很多文献上分而治之算法（与O(n logn)复杂性），我会感谢有关上述解决方案的一些参考。

来源

2015-07-19 oski86

这可以帮助吗？ http://stackoverflow.com/questions/337664/counting-inversions-in-an-array - 有一些'O（n日志n）'解决方案，我认为这表明你是最低的可以去... –

您发布的算法不是线性'O（n）'，因为它是递归调用'inv_count（ones，m）'。它是'O（n * log n）'。 – Onheiron

嗯，这很有趣。我在'Python'中做了一个简单的timeit脚本，它显示出一个经典的“分而治之”的解决方案比使用按位操作...：https：//gist.github的代码快得多（2-3倍）。 com/oskar-j/f9bb24e4c390cedd3216 – oski86

它是O（n w），其中最大值小于2^w。如果w = 32，如代码所假定的那样，那么是的，这是一个线性时间算法。另一方面，对于至多有d个不同元素的输入，存在基于O（n log d）时间比较的算法，当d = 2^w = 2^32时这也是线性的。 Ω（n log n）时间下限适用于所有输入元素可能不同的基于比较的算法。

来源

2015-07-19 11:56:18

这种指称n日志排序的名称是什么？ :) –

@NiklasB。我不知道名字。我认为它是一种计数排序模拟，它在≤d键上扩展基于BST的映射，对值进行前缀总和。 –

是的，它是线性的数值是受限制的（32位）。

它与计数排序（https://en.wikipedia.org/wiki/Counting_sort）类似，用于排序。

来源

2015-07-19 11:58:38

这是用于计算数组O（n）复数中的倒数的算法吗？

回答

相关问题