我的堆排序算法时间复杂度分析是否正确？

Question

算法如下：

void heapSort(int * arr, int startIndex, int endIndex)
{
    minHeap<int> h(endIndex + 1);

    for (int i = 0; i < endIndex + 1; i++)
        h.insert(arr[i]);

    for (int i = 0; i < endIndex + 1; i++)
        arr[i] = h.deleteAndReturnMin();
}

方法insert()和deleteAndReturnMin()都是O(log n)。 endIndex + 1可以称为n个元素。因此，鉴于这些信息，我说第一个和第二个循环都是 O(n log n) 并且因此整个算法的时间复杂度是 O(n log n) 是否正确？更准确地说，总时间复杂度是否为 O(2(n log n))（不包括初始化）？我正在学习大 O 表示法和时间复杂度，所以我只想确保我理解正确。

Answer 1

你的分析是正确的。

鉴于您提供的两种方法是对数时间，您的整个运行时间是对数时间迭代 n 个元素 O(n log n) 总计。你也应该意识到Big-O符号忽略了常数因子，所以因子2是没有意义的。

请注意，您的代码中存在错误。输入似乎表明数组从 startIndex 开始，但 startIndex 在实现中被完全忽略。

您可以通过将堆大小更改为 endIndex + 1 - startIndex 并从 int i = startIndex.

开始循环来解决此问题