2

我对使用 big-O 表示法确定算法运行时间的做法相对较新，并且我对排序算法的运行时间有疑问。假设我在一个数组中有一组对 (a, b)，我使用已知的排序算法对数据进行排序，该算法在 O(n log n) 中运行。接下来，我取一些 n 个数据点的子集，并在该子集上运行相同的排序算法（所以理论上我可以对整个数组进行两次排序——第一次排序将比较 a，第二组将比较 b） . 所以换句话说我的代码是

pairArray[n];
Sort(pairArray); //runs in O(n log n)

subsetArray[subset]; //where subset <= n
for (int i = 0; i < subset; i++) {
   subsetArray[i] = pairArray[i];
}

Sort(subsetArray) //runs in O(n log n)

这段代码的运行时间仍然是 O(n log n) 吗？我想我有两个问题：运行 O(something) 排序两次是否会增加原始“某物”的复杂性，并且重新分配给不同数组的迭代是否会增加复杂性？我更担心第一个，因为可以用指针消除迭代。

4

1 回答 1

4

在大 O 表示法中忽略了接触因子。排序两次仍然是 O(n log n)。

您正在执行的分配循环是 O(n) 操作。这也被忽略了。大 O 表示法中只提到了最大的项。

如果您想确定两种算法中哪一种更好，但它们的大 O 相同，那么您可以对真实数据使用性能测量。在测量实际性能时，您可以查看一种算法是否通常比另一种慢两倍。这不能从大 O 表示法中看出。

于 2012-10-06T06:28:25.513 回答