Big-O Runtime для созданной программы - PullRequest
Новая
       6

Big-O Runtime для созданной программы

0 голосов
/ 29 ноября 2018

Я пытаюсь создать код, который запускается в определенное время.Мой первый метод должен работать в худшем случае в 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) как в линейном?

1 Ответ

0 голосов
/ 29 ноября 2018

Давайте сделаем эту строку построчно. 

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: O(1 * log k), то есть O(log k).
  2. Если оно идетв else if блок: 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).Поскольку это будет выполнено вне цикла, сложность по времени не будет умножена.

...