我正在尝试创建在特定时间运行的代码。我的第一个方法最坏的运行时间应该是 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) 呈线性吗?
最佳答案
让我们逐行执行此操作。
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
block :O(1 * log k)
,即O(log k)
。 - 如果进入
else if
block :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)
。由于这将在循环之外执行,因此时间复杂度不会成倍增加。
关于java - 用于程序制作的 Big-O 运行时,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53530427/