java - 用于程序制作的 Big-O 运行时

Question

我正在尝试创建在特定时间运行的代码。我的第一个方法最坏的运行时间应该是 O(log k)。这是我的方法:

public void count(T x) {
    if(heap.size() < k){
        heap.add(x);
    }
    else if(heap.size() == k && x.compareTo((T) heap.peek()) > 0){
        heap.remove(); 
        heap.add(x);
    }
}

我在计算运行时间时遇到问题。我很确定 heap.size() 调用是恒定时间。而 add() 方法的运行时间为 O(log k)。这对于remove()方法来说也是如此。其他比较也应该只需要恒定的时间。因此我非常确定我的程序运行时间为 O(log k)。有人可以确认一下吗？

我的另一个方法应该在 O(k log k) 时间内运行。这是我的方法:

public List<T> kbest() {
    //empty queue first and then restore
    List<T> list = new ArrayList<T>();
    int size = heap.size(); 
    for(int i = 0; i < size; i++){
        list.add(0, heap.poll());
    }
    for(int j = 0; j < list.size(); j++){
        heap.add(list.get(j));
    }
    return list;
}

这个对我来说比较难以理解。列表中的 add() 以恒定时间运行。而堆中的 add() 运行时间为 O(log k)。获取堆的大小是恒定的，列表的大小也是恒定的(完成“j”次)。这会使我的运行时间 O(n) 呈线性吗？

Answer 1

让我们逐行执行此操作。

public void count(T x) {
    if(heap.size() < k){ // O(1)
        heap.add(x); // O(log k)
    }
    else if(heap.size() == k && // O(1)
                x.compareTo(
                    (T) heap.peek()) > 0) { // O(1)
        heap.remove(); // O(log k)
        heap.add(x); // O(log k)
    }
}

1. 如果进入 if block :O(1 * log k)，即 O(log k)。
2. 如果进入else if block :O(max(1, 1) * max(log k, log k))，即O (log k)。
3. 所以你是对的 - 该方法的时间复杂度为 O(log k)。

现在是第二种方法:

public List<T> kbest() {
    //empty queue first and then restore
    List<T> list = new ArrayList<T>();
    int size = heap.size();  // O(1)
    for(int i = 0; i < size; i++) { // O(n)
        list.add(0, heap.poll()); // O(n)
    }
    for(int j = 0; j < list.size(); j++){ // O(n)
        heap.add(list.get(j)); // O(log n)
    }
    return list;
}

1. heap.size 为 O(1)。
2. 第一个 for 循环的时间为 O(n * n)，即 O(n^2)。
3. 第二个 for 循环的时间复杂度为 O(n * log n)，即 O(n log n)。
4. 最终复杂度为 O(max(1, n^2, n log n))，即 O(n^2)。

更新

要提高kbest()的时间复杂度，可以使用add()方法，其时间复杂度为O(1)。

当然，顺序可以颠倒过来。您可以轻松使用Collections.reverse(list)，这将是O(n)。由于这将在循环之外执行，因此时间复杂度不会成倍增加。