當比較花費任何時間

我要排序的陣列，A，根據本成本模式排序：當比較花費任何時間

對於任何x值，形式A的分配[I] = x具有的成本1.另外，A [i] = A [j]的成本爲1.
其他操作，如比較和分配for x = A [i]（其中x不是陣列）的成本爲0.

問題：

給一個下界排序的陣列A.你的答案應該是在正方面的精確表達式，而不是使用漸近記法所要求的最壞情況下的時間。
描述使用O（n）空間的排序算法。運行時應該與1中給出的下界完全匹配（確切地說，不是漸近地）。
描述對這個成本模型最優的就地排序算法。運行時應該完全匹配1中給出的邊界（完全不是漸近地）。

我嘗試：

ñ。這是因爲，在最糟糕的情況下，數組中的n個元素處於索引中，因此它們將不需要處理。因此，需要n個賦值才能按排序順序獲取數組。

我的算法psudo代碼：

def weird_sort(A): 
    B = an array the same size of A 
    C = an array of bools (default True) the same size of A 
    for i in range(0, A.size): 
     min = first index in c that is True 
     for j in range(0, A.size): 
      if (A[j] < A[min]) and (C[j]): 
       min = j 
     B[i] = A[min] 
     C[i] = False 
    A = B

我認爲這恰恰是N次跑，因爲我們正在進入一個指定任何唯一的一次是在最後一行，在那裏我們複製B的內容變成A.

不知道從哪裏開始。在我看來，爲了保持一切到位，我們必須交換數組A中的東西，但是我無法弄清楚如何去掉如何用n/2交換對數組進行排序。有人能讓我朝着正確的方向前進嗎？你也可以仔細檢查我的答案1和2嗎？

來源

2017-10-22 Jean Hans

這可能是一個更好的問題https://cs.stackexchange.com/ – Stedy

這聽起來像循環排序發明的確切情況。 :-) – templatetypedef

我認爲就地允許O(1)額外變量，因爲否則我不認爲這是可能的

首先讓解決子問題：鑑於i，發現這應該是上個i位置的數字。因爲比較是免費的，所以可以使用bruteforce。

現在複製第一個元素（到附加變量），找到最小的元素並將其放在位置1.現在這個元素位於i的位置。讓我們找到應該在位置i上的元素並將其複製到此處（假設它位於位置j），現在找到屬於位置j等的元素。最後，我們找到了我們最初複製的元素，將其放回。因此，我們使用k賦值（在循環結構中）將k變量設置爲它們的位置。現在對所有其他元素都做同樣的事情。你無法記住每個變量是否放在原處，但是你可以檢查它是否在它的位置上是免費的。

如果有一本相等的元素應該慎重些，但儘管談論高效排序算法時，它仍然應該工作

來源

2017-10-22 01:59:39 RiaD

，我們通常會傾向於對快速排序講，這種算法進行了優化比較次數。

但是，其他算法嘗試優化內存訪問的次數（與您的情況一樣）。其中一些被稱爲緩存遺忘算法（不對特定內存層次結構參數進行假設）和緩存感知（針對特定內存層次結構進行調整）。你可以找到這種算法，所以你可能有興趣給他們看看。

作爲一個例子，Harald Prokop's PhD thesis討論了緩存遺忘算法，並提出了分配排序，它將子組中的數據部分排序，這些子組可能適合存儲器層次結構的較低分區。

分佈排序使用O(n ln(n))工作，並會導致O(1+ (L/n)*(1+logz(n))高速緩存未命中ň元素進行排序。

其中大號是一個高速緩存銀行的規模和ž緩存本身的大小。性能模型只假定只有一個高速緩存級別，但由於不知情的屬性而適應所有高速緩存級別。

其基本概念是分配成本根據元素放置在內存層次結構中的位置而變化。

來源

2017-10-23 08:21:44

當比較花費任何時間

回答

相關問題