這是用於計算數組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）複數中的倒數的算法嗎？

回答

相關問題