Program Made 的 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() 方法运行s 在 O(log k) 时间内。 remove() 方法也是如此。另一个比较也应该只需要一个常数时间。因此我很确定我的程序运行s 在 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() 在列表运行s 中以常数时间。而 add() 在堆中运行s 在 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)
    }
}

如果它进入 if 块：O(1 * log k)，即 O(log k)。
如果它进入 else if 块：O(max(1, 1) * max(log k, log k))，即 O(log k)。
所以你是对的 - 这个方法是 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;
}

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

更新

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

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

Program Made 的 Big-O 运行时

Big-O Runtime for Program Made

java

heap

time

big-o

list

更新