Как определить Big-Oh для анализа времени выполнения? - PullRequest
Новая
       16

Как определить Big-Oh для анализа времени выполнения?

0 голосов
/ 11 декабря 2018

Я пытаюсь выполнить анализ времени выполнения для метода класса "SlowMaxStack" IsEmpty (), Push (), Pop () и getMaxSoFar ().

Вот мое предположение, но я не уверен, что ответ правильный, и я также сомневаюсь в своих рассуждениях.

IsEmpty (): o (1), просто проверьте верхний узел.константа

Push (): o (1), просто помещая данные в верхний узел.константа

Pop (): o (1), предполагая, что это может быть o (3), но все еще константа, поэтому я думаю, что это o (1)

getMaxSoFar (): o (n), поскольку цикл for проходит элемент до длины элемента node.Сверху 1 + n + 1 -> n + 2 -> o (n) 

class ListNode<T>{
public T value;
public ListNode<T> next;

public ListNode(T value, ListNode<T> next)
{
    this.value = value;
    this.next = next;
}

public ListNode<T> setValue(T value) 
{
    return new ListNode<T>(value, this); 
}
}

interface Maximizer<T> {
T getMax(T t1, T t2);
T getGlobalMin();
}

interface MaxStack<T> 
{
boolean isEmpty();

void push(T value);

T pop();

T getMaxSoFar();
//returns the maximum value in the stack
}


class SlowMaxStack<T> implements MaxStack<T>  
{
private final Maximizer<T> maximizer; //data 
private ListNode<T> top; // node 

public SlowMaxStack(Maximizer<T> maximizer) 
{
    this.maximizer = maximizer;
}

@Override
public boolean isEmpty() 
{
    return top == null;
}

@Override
public void push(T value)
{
    if (top == null)
    {
        top = new ListNode<T>(value, null);
    } 
    else 
    {
        top = top.setValue(value);
    }
}

@Override
public T pop() 
{
    T value = top.value;
    top = top.next;
    return value;
}

@Override
public T getMaxSoFar() 
{
    T currentMax = maximizer.getGlobalMin();

    for(ListNode<T> node = top; node != null; node = node.next) 
    {
        currentMax = maximizer.getMax(currentMax, node.value);
    }   
    return currentMax;
}
}
...