求堆函数的复杂性

Question

我将为堆排序使用以下代码(链接：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+ N_log(N)，它简化为N_log(N)。通常，您不会逐行进行这种分析，而是只需查找代码中涉及迭代的每一个位置，但这种方式是可行的。