交换数在排序算法分析中的重要性--三分法

Question

我正在开发一个三向分区算法来对数据进行排序。我可以观察到，对于大数据集中的几个不同的元素，算法进行的比较比传统版本的快速排序要少。

然而，掉期交易的数量高于正常版本的快速排序.

为了对算法进行分析，我需要了解掉期次数的影响以及比较对整个算法性能的影响。

Answer 1

当用静态分析分析算法的效率时--即不实际运行代码和测量算法所需的时间--我们通常只关注算法的渐近复杂性，这可以用大O符号和相关的渐近表示来描述。

关于大O表示法的一个重要事实是，O(f + g)要么是O(f)，要么是O(g)，两者以较大者为准。所以，如果f测量你的算法做了多少比较，g测量多少个掉期，那么无论哪个比较大，都是最重要的。两者都对算法的实际运行时间有影响，但只有较大的影响才会影响算法的渐近运行时间。

大多数排序算法比掉期算法做更多的比较，所以通常比较的数量才是最重要的。但是如果你的算法比比较做更多的交换，那么掉期的数量对你的算法来说才是最重要的。

当然，如果您的算法还有其他操作，如加法、乘法、读取或分配内存分配，那么您也应该考虑这些操作。无论您的算法执行的是哪一种操作，都将决定它的渐近运行时间。