Notazione Big-Oh di uno stackarray

-1

Sto studiando le strutture dati e ho colpito un po 'un blocco stradale. La parte superiore è Big oh notation ed è semplicemente confusa. Mentre riesco a trovare il limite superiore per i loop più semplici, quando si tratta di cose più complicate, mi sento un po 'perso.

Ho questo programma di array stack Java che sto usando come pratica e speravo che qualcuno qui potesse mostrarmi come trovare il limite superiore.

Codice:

import jeliot.io.*;

public class IStack {
   private int maxSize;
   private long[] stackArray;
   private int top;
   public IStack(int s) {
      maxSize = s;
      stackArray = new long[maxSize];
      top = -1;
   }
   public void push(long j) {
      stackArray[++top] = j;
   }
   public long pop() {
      return stackArray[top--];
   }
   public long peek() {
      return stackArray[top];
   }
   public boolean isEmpty() {
      return (top == -1);
   }
   public boolean isFull() {
      return (top == maxSize - 1);
   }
   public static void main(String[] args) {
      IStack NStack = new IStack(5); 
      NStack.push(0);
      NStack.push(1);
      NStack.push(2);
      NStack.push(3);
      NStack.push(4);
      while (!NStack.isEmpty()) {
         long value = NStack.pop();
         System.out.print("value: " + value);
         System.out.print(" ");
      }
      System.out.println("");
   }
 }
    
posta Liwizy 22.09.2016 - 00:32
fonte

1 risposta

1

Big-O non si applica alle classi. Si applica agli algoritmi, ad esempio i metodi. Non è raro che una struttura dati abbia un O grande-grande per operazioni diverse come l'inserimento, la cancellazione, ecc.

Inoltre, big-O si applica solo agli algoritmi / metodi che operano su un input di dimensioni variabili (il n ). È solo il caso dei metodi push , pop e peek , che opera sui dati dello stack. Metodi come isFull non operano alcun input di dimensioni variabili, quindi O grande non si applica.

Lo stack utilizza un array come storage sottostante. I metodi push , pop e peek eseguono un singolo accesso indicizzato all'array sottostante. Poiché gli array hanno accesso O (1) agli elementi, i metodi push , pop e peek hanno anche la complessità O (1).

Questo significa che hai uno stack molto efficiente. Ma il problema ovvio è che la dimensione è limitata a maxSize . Quando lo stack diventa più grande, si bloccherà. Quindi, in pratica, devi essere in grado di far crescere l'array, il che renderà l'algoritmo più interessante.

Il metodo main è un po 'complicato. Poiché si definiscono i dati di input con una dimensione fissa (5 elementi), l'operazione è anche tecnicamente costante. Non ci sono input di dimensioni variabili qui. Ma probabilmente vuoi conoscere il big-O del ciclo while, se lo stack di input è di dimensioni arbitrarie. Probabilmente lo puoi capire ora sai che pop è O (1).

    
risposta data 22.09.2016 - 08:30
fonte

Leggi altre domande sui tag