最高分類操作

任何分類算法的最耗費操作是什麼？它是交換操作還是比較操作？最高分類操作

我以爲這是交換，但我的朋友認爲它的比較。我可以證明這種比較的唯一方法是成本較高的操作，即每個元素都需要進行比較，但不是每個元素都需要進行交換（即，如果元素已經處於正確的位置，則不必交換）。因此，從總體上看，比起幾次昂貴的掉期來說，便宜的比較更爲便宜。但我不確定答案。有什麼想法嗎？

來源

2012-05-12 Bugaboo

這取決於。對於基於磁盤的數據，主要因素是將磁盤頁面放入內存所需的I/O。一旦頁面出現，CPU就相對免費。對於小型密鑰（整數），交換可能比比較成本高。對於非常小的元素大小，內存（緩存）位置可能占主導地位。 – wildplasser

（從wildplasser繼續）......這意味着磁盤（或虛擬內存）上的列表生存，交換成本更高。但是，如果列表存在於高速緩存中，那麼交換和比較大體上是（有序的）相似的花費，然後所有交換或所有比較的累積成本取決於您使用的算法。 –

假設一切都完成到RAM中，交換操作比比較操作的原子速度快。（這是非常明顯的，2讀取然後一個CPU操作與2讀取，2寫入和包括註冊表操作之間的一切）。

這顯然取決於你的排序算法，有些做比較少，因爲有更少的元素，但交換相對更經常。

採取快速排序，將做幾個比較，然後交換幾乎所有的東西和一個簡單的算法，如泡沫排序，比較所有的元素與對方，然後交換次數較少。這也取決於基本數組，如果一切已經接近排序，冒泡排序不會交換任何東西，但仍然會比較所有內容，而堆排序（例如）仍然必須「交換」所有內容。

最後（交換操作的平均數量）（交換操作的時間成本）/（CoMP操作的平均數量）（CoMP操作的時間成本）是相當難的算法來估算，這是一個很大更多的外推到所有的算法。

我個人認爲，任何排序算法的交換成本總是高於比較成本，但我不能用任何證據（這只是個人見解）來支持這一說法。

來源

2012-05-12 18:19:03 AdrienNK

我不太明白，當一切都在RAM中時，交換的明顯部分變得更便宜：（ – Bugaboo

）在一個非常簡化的計算機（不包括頁面文件的概念等，因爲它增加了大量的隨機性），如果你的數組是在ram爲了比較兩個值，你必須將兩個值加載到註冊表中，然後使用ALU比較兩個值。爲了交換，必須記住註冊表中的兩個RAM地址，然後將這兩個值存入其他註冊表中，然後使用RAM寫入第一個值的地址寫第二個值等我可以向你解釋爲什麼它需要更長的時間，但我將不得不向你解釋其他概念，如週期，微碼等。 – AdrienNK

以上的事情與預防措施，這是一個簡化系統，更高級的使用流水線，這增加了另一層複雜性如果你真的想知道這個問題的一切，我建議你閱讀和學習n關於計算結構/計算機設計，因爲在考慮操作成本時這真的很重要。如果你已經有一些更容易解釋的程序集。 – AdrienNK

最高分類操作

回答

相關問題