查找堆函数的复杂度

Question

我将使用下面的代码进行堆排序(Link: https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/Heap.java)

给定以下代码：

public static void sort(Comparable[] pq) {                     // Complexity: O(NLog N)
    int n = pq.length;                                         // Complexity: O(1)
    for (int k = n/2; k >= 1; k--)                             // Complexity: O(N)
        sink(pq, k, n);                                        // Complexity: O(Log N)
    while (n > 1) {                                            // Complexity: O(N)
        exch(pq, 1, n--);                                      // Complexity: O(1)
        sink(pq, 1, n);                                        // Complexity: O(Log N)
    }
}

private static void sink(Comparable[] pq, int k, int n) {      // Complexity: O(Log N)
    while (2*k <= n) {                                         // Complexity: O(Log N)
        int j = 2*k;                                           // Complexity: O(1)
        if (j < n && less(pq, j, j+1)) j++;                    // Complexity: O(1)
        if (!less(pq, k, j)) break;                            // Complexity: O(1)
        exch(pq, k, j);                                        // Complexity: O(1)
        k = j;                                                 // Complexity: O(1)
    }
}
private static boolean less(Comparable[] pq, int i, int j) {   // Complexity: O(1)
    return pq[i-1].compareTo(pq[j-1]) < 0;                     // Complexity: O(1)
}
private static void exch(Object[] pq, int i, int j) {          // Complexity: O(1)
    Object swap = pq[i-1];                                     // Complexity: O(1)
    pq[i-1] = pq[j-1];                                         // Complexity: O(1)
    pq[j-1] = swap;                                            // Complexity: O(1)
}

我想知道我的想法是否正确？？我在这个领域有点菜鸟。

Answer 1

你的逻辑看起来是正确的。排序函数是 N + Nlog(N)，它确实简化为 Nlog(N)。通常，您不会逐行进行此类分析，而只是查找代码中涉及迭代的每个地方，但这种方式有效。

查找堆函数的复杂度

Finding complexity of heap function

complexity-theory

time-complexity

code-complexity

heapsort

space-complexity